• 题目: 洛谷

思路

输入

389 207 155 300 299 170 158 65

输出

6
2

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
int w[N],dp[N],f[N],n = 1;

int main(){
    while(scanf("%d",&w[n]) == 1) ++n;

    int len = 0;
    dp[0] = 0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        int l = 0 , r = len;
        while(l < r){
            int mid = l + r + 1>> 1;
            //后一发导弹不高于前一发
            if(dp[mid] >= w[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len,l + 1);
        dp[l+1] = w[i];
    }
    // for(int i=1;i<=len;++i) cout << dp[i] << " ";
    // cout << endl;
    cout << len - 1 << endl;

    int cnt = 1;
    for(int i=1;i<=n;++i){
        int k = 1;
        while(k < cnt  &&  f[k] < w[i]) ++k;

        f[k] = w[i];
        if(k >= cnt) ++cnt;
    }
    cout << cnt - 1 << endl;
    return 0;
}