2023年4月2日
https://vjudge.csgrandeur.cn/contest/550913#problem/G 注意到网上没有什么贪心做法的证明，就发一篇出来
我的思路
没看出来是个dp，就想想贪心。 扫描数组，找到第一个没出现过的，设为最大值，cnt++，以其为起点，再一重循环往下扫描，比最 大值小的就标记，然后更新最大值， n方复杂度，和dp差不多
卡壳点
一个是多组输入没有初始化，再就是在第二重的j指针扫描里，伪代码的描述有缺漏，应该要扫到比最大值小且没标记过的
贪心证明
主要要证明的就是拦截系统拦截第一个导弹能得到最优方案的问题 不需要考虑哪个拦截系统系统的高度亏损，高的拦截中的，中的拦截小的 ，和高的拦截小的，中的拦截中的最终结果都是得到一个中一个小的拦截系统，位置也是相同的，所以两种方案等价，
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e3 + 10; int a[N]; bool st[N]; int main(){ int n; while(~scanf("%d",&n)){ int cnt = 0; for(int i = 1;i <= n;i++){ cin >> a[i]; } memset(st,0,sizeof st); for(int i = 1;i <= n;i++){ int maxn ; if(!st[i]){ maxn = a[i]; cnt++; for(int j = i+1;j <= n;j++){ if(maxn >= a[j] && !st[j]) {st[j] = true,maxn = a[j]; // cout << a[j]<< endl;/ } } } } cout << cnt << endl; } return 0; }
