首页 > 代码库 > AC日记——导弹拦截 洛谷 P1020 (dp+模拟)
AC日记——导弹拦截 洛谷 P1020 (dp+模拟)
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出格式
输入格式：
一行，若干个正整数最多100个。
输出格式：
2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出样例
输入样例#1：
389 207 155 300 299 170 158 65
输出样例#1：
62
思路：
LIS+模拟=不难就是恶心
来，上代码：
#include<cstdio>#include<algorithm>using namespace std;int ai[101],f[101],ans_max,ans_num=1,n,cur_2;int main(){ //scanf("%d",&n); //for(int i=1;i<=n;i++) scanf("%d",&ai[i]),f[i]=1; n=0; while(scanf("%d",&cur_2)==1) { n++; f[n]=1; ai[n]=cur_2; } for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { if(ai[i]<=ai[j]) { f[i]=max(f[j]+1,f[i]); } } } for(int i=1;i<=n;i++) ans_max=max(ans_max,f[i]); printf("%d\n",ans_max); for(int i=1;i<=n;i++) { if(f[i]!=ans_max) continue; int cur_1=ans_max; int now=ai[i]; ai[i]=0; cur_1--; for(int j=i-1;j>0;j--) { if(cur_1==0) break; if(cur_1==f[j]&&ai[j]>=now) now=ai[j],ai[j]=0,cur_1--; } break; } for(int i=2;i<=n;i++) { if(ai[i-1]==0) { for(int j=i-1;j>0;j--) if(ai[j]==0) swap(ai[j],ai[j+1]); } } int before=n; n-=ans_max; while(n!=0) { ans_num++; 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(ai[i]<=ai[j]) f[i]=max(f[j]+1,f[i]); } } ans_max=0; for(int i=1;i<=n;i++) ans_max=max(ans_max,f[i]); for(int i=1;i<=n;i++) { if(f[i]!=ans_max) continue; int cur_1=ans_max; int now=ai[i]; ai[i]=0; cur_1--; for(int j=i-1;j>=0;j--) { if(cur_1==0) break; if(cur_1==f[j]&&ai[j]>=now) now=ai[j],ai[j]=0,cur_1--; } break; } for(int i=2;i<=n;i++) { if(ai[i-1]==0) { for(int j=i-1;j>0;j--) if(ai[j]==0) swap(ai[j],ai[j+1]); } } n-=ans_max; } ans_num+=n; printf("%d\n",ans_num); return 0;}
AC日记——导弹拦截 洛谷 P1020 (dp+模拟)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。