1010. 拦截导弹
题意
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
思路
第一小问是裸的最长上升子序列
第二步 贪心地考虑两种情况
情况1：如果现有的子序列的结尾都小于当前数，则创建一个新的子序列
情况2：将当前的数放到结尾大于等于它的最小的子序列的最后
证明：设正确答案子序列个数为 b 设按照上面所述方法得到的子序列个数为 a
因为 b 是正确答案 所以一定有 b≤a
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 6000; int n; int a[N]; int q[N]; //q[i] 表示长度为 i 的下将子序列的最后一个数字的最大值 int g[N]; void solve() { int cnt = 0; while (scanf("%d", &a[cnt]) != EOF)cnt++; int len = 0; for (int i = 0; i < cnt; ++i) { //最长下降子序列 int l = 0, r = len; while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] >= a[i]) l = mid; else r = mid - 1; } len = max(len, r + 1); q[r + 1] = a[i]; } cout << len << endl; int id = 0; for (int i = 0; i < cnt; ++i) { int k = 0; while (k < id && a[i] > g[k])k++; g[k] = a[i]; if (k >= id)id++; } cout << id << endl; } int main() { //int t; cin >> t; //while (t--) solve(); return 0; }
