调试了一个晚上,还是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;
}