[Acwing] 1010. 拦截导弹

https://www.acwing.com/problem/content/description/1012/

问题分析

两个问题

• 求最长下降子序列
• 最少用多少个下降子序列 才能填满 区间

思路

第一问 直接变化转移方程即可 或者 reverse一下

第二问 贪心的求子序列即可

从前往后扫描每个数，对于每个数：

• 情况1：如果现有的子序列的结尾都小于当前数， 则创建新子序列
• 情况2: 将当前数放到结尾大于等于它的最小的子序列后面

其他收获

y总的字符串处理:

   string line;
    getline(cin, line);
    stringstream ssin(line);
    while (ssin >> h[n]) n ++ ;

CODE:

#include 
using namespace std;
const int N =  1e3+10;
int f[N],a[N],idx,q[N];

void s_to_int()
{
    string s;
    getline(cin,s);
    s+=' ';
    memset(a,0,sizeof a);
    int l = 0 ;

    int len = s.size();
    for(int i = 0; i