无助的蒟蒻
查看原帖
无助的蒟蒻
854995
flyWang楼主2023/10/9 21:21

调试了一个晚上,还是150分,乞求大神援助T_T

#include<bits/stdc++.h>
using namespace std;
int len, a[50005], b[50005];
int main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    //最长不上升子序列
    //到时候倒着输入 从小到大
    //最多拦截多少导弹好算,但是至少几套系统的这个怎么想??
    int cnt = 0;
    while (cin >> a[++cnt]);
    cnt--;
    //for (int i = 0; i < cnt; ++i)cout << a[i] << "   ";
    //最长不上升子序列
    //翻转过来就是最长非下降子序列
    len = 0;
    b[0] = a[cnt];
    for (int i = cnt - 1; i >= 1; --i) {
        if (a[i] >= b[len])b[++len] = a[i];
        else {
            //找第一个比我小的 ???? 其实是找第一个比我小的
            /*for (int i = 0; i <= len; ++i) cout << b[i] << '\t';
            cout << endl;*/
            //找第一个比我大的
            auto j = upper_bound(b,b + len + 1,a[i]) - b;
            b[j] = a[i];
           /* for (int i = 0; i <= len; ++i) cout << b[i] << '\t';
            cout << endl;*/
        }
    }
    //for (int i = 0; i <= len; ++i) cout << b[i] << '\t';
    cout << len + 1<< endl;
    //现在求这个最长上升子序列
    len = 0;
    b[0] = a[1];
    for (int i = 2; i <= cnt; ++i) {
        if (a[i] > b[len])b[++len] = a[i];
        else {
            int j = lower_bound(b, b + len + 1, a[i]) - b;
            b[j] = a[i];
        }
    }
    cout << len + 1<< endl;
    return 0;
}

2023/10/9 21:21
加载中...