拦截导弹

题目链接

思路:

  第一个问题很好解决，就是最长不上升子序列，利用贪心 + 二分的dp就可以解决，这里给一个二分查找的函数
 二分查找

 第二个问题是问给出的序列最少可以分成几个不上升子序列，其实这里有一个定理
 由Dilworth 定理，不上升子序列的最小划分数为 a 的最长上升子序列长度。
所以第二个问题就转化为了求这个序列的最长上升子序列，其实如果要省事的话，可以把这个序列颠倒过来，然后就转化为第一个问题

code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 5;

int dp[maxn],a[maxn];
int n = 1;

void Solve()
{
    memset(dp, 0, sizeof dp);
    //先求最长不上升子序列
    int ans= 1;
    dp[ans] = a[1];
    for(int i = 2; i <= n; i++){
        if(a[i] <= dp[ans]) dp[++ans] = a[i];
        else{
            //找到第一个小于等于a[i]的数字
            int idx = lower_bound(dp + 1, dp + ans, a[i],greater<int>()) - dp;
            dp[idx] = a[i];
        }
    }
    cout<<ans<<endl;
}

int main()
{
    while(cin>>a[n]) n++;
    n--;
    Solve();
    //由Dilworth}Dilworth 定理，不上升子序列的最小划分数为 a 的最长上升子序列长度。
    reverse(a + 1, a + n + 1);
    Solve();
    return 0;
}