首页 > 代码库 > [NOIP1999]拦截导弹 DP
[NOIP1999]拦截导弹 DP
题目描述题目链接 请点击
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入格式
输入数据为两行，
第一行为导弹的数目N(n<=1000)
第二行导弹依次飞来的高度，所有高度值均为不大于30000的正整数。
输出格式
View Code
1.输出只有一行是这套系统最多能拦截的导弹数和 2.要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6 2
可以先将这个问题分作两个小问题解决，第一个小问明显是要求出最长非严格下降子序列，因为它要保证每一发炮弹都不能高于前一发的高度
第二个小问则是要你求出最长严格上升子序列，这个结论就不能明显的出啦，因为一开始我也想不出来，也是看了题解才懂。
证明过程：
目标首先是要保证所有的目标都要摧毁，既然每个目标都要被摧毁，那么如果这个被摧毁的目标的后面的目标比它搞的话，摧毁这个目标
的导弹系统就不能摧毁它后面的目标了。从而，我们所需要的炮弹系统的高度必定是严格上升的序列~又因为要摧毁所有的目标，所以为最长严格
上升子序列~
ps：这道题的数据目测比较弱，第二问我用非严格上升去做也能ac。。。。。
附上ac的c++代码：
1 #include <cstdio> 2 #include <iostream> 3 4 using namespace std; 5 const int maxn = 1111; 6 int a[maxn],inc[maxn],dece[maxn]; 7 const int INF = 0x3f3f3f3f; 8 int main(){ 9 int n;10 while(~scanf("%d",&n)){11 int INC = 0,DEC = 0;12 fill(a,a + maxn,0);13 fill(inc,inc + maxn,0);14 fill(dece,dece + maxn,0);15 for(int i = 1;i <= n;++i)16 scanf("%d",&a[i]);17 a[0] = INF;//注意 初始化18 for(int i = 1;i <= n;++i){19 for(int j = 0;j <= i-1;++j){20 if(a[i] <= a[j]&&dece[i] < dece[j] + 1) //非严格下降子序列21 dece[i] = dece[j] + 1;22 }23 //cout<<dece[i];24 DEC = max(DEC,dece[i]);25 }26 //cout<<endl;27 a[0] = -INF;//注意重新初始化28 for(int i = 1;i <= n;++i){29 for(int j = 0;j <= i-1;++j){30 if(a[i] > a[j]&&inc[i] < inc[j] + 1) //严格上升子序列31 inc[i] = inc[j] + 1;32 }33 //cout<<inc[i];34 INC = max(INC,inc[i]);35 }36 //cout<<endl;37 printf("%d %d\n",DEC,INC);38 }39 return 0;40 }
[NOIP1999]拦截导弹 DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。