AcWing 1010. 拦截导弹
原题链接
简单
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, x;
int a[N];
int f[N];
vector<int> vec[N];
int cnt;
int main() {
while (scanf("%d", &x) != EOF) a[++n] = x;
// 求最长下降子序列
for (int i = 1; i <= n; i++) f[i] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, f[i]);
printf("%d\n", res);
// 统计下降子序列的数量
for (int i = 1; i <= n; i++) {
int l = 0, r = cnt - 1;
while (l < r) {
int mid = l + r >> 1;
if (vec[mid].back() >= a[i]) r = mid;
else l = mid + 1;
}
if (!vec[l].size()) vec[cnt++].push_back(a[i]);
else if (vec[l].back() < a[i]) vec[cnt++].push_back(a[i]);
else vec[l].push_back(a[i]);
}
printf("%d", cnt);
return 0;
}