@[Daniel141130](/user/952596) 读题，题目说的是**以后每一发炮弹都不能高于前一发的高度**。
by VividCycle @ 2023-12-08 08:33:43
现在NOIP原数据过了
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, cnt, b[50005], a[50005], minj, dp[50005], ans;
int main () {
while (cin >> a[++n]);
n--;
for (int i = n; i > 0; i--) {
dp[i] = 1;
for (int j = i + 1; j <= n; j++) {
if (a[i] >= a[j])
dp[i] = max (dp[i], dp[j] + 1);
//cout << dp[j] << endl;
}
//cout << a[i] << endl;
//cout << dp[i] << endl;
ans = max (dp[i], ans);
}
cout << ans << endl;
for (int i = 1; i <= n; i++) {
b[0] = 1e9 + 5;
minj = 0;
for (int j = 1; j <= cnt; j++) {
if (b[j] >= a[i] && b[j] < b[minj]) {
minj = j;
}
}
if (minj == 0) {
b[++cnt] = a[i];
} else {
b[minj] = a[i];
}
}
cout << cnt << endl;
return 0;
}
```
by Daniel141130 @ 2023-12-08 09:24:03
@[Daniel141130](/user/952596) 你这个方法是 $\mathcal{O}(n^{2})$ 的当然只能过前面的数据，去学习一下 $\mathcal{O}(n \log n)$ 的方法。
by VividCycle @ 2023-12-08 09:26:52
如何用n log n
此处a数组不一定是排好序的而且如果排序又会破坏数据
by Daniel141130 @ 2023-12-08 09:28:56
@[Daniel141130](/user/952596) 二分。不过似乎不是在 a 数组里二分，而是在 dp 数组里二分。
by xiaoshumiao @ 2023-12-08 10:21:54