[NOIP1999]拦截导弹 DP

  题目描述题目链接 请点击

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入格式

输入数据为两行,

第一行为导弹的数目N(n<=1000)

第二行导弹依次飞来的高度,所有高度值均为不大于30000的正整数。

输出格式

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 }

时间: 10-05

[NOIP1999]拦截导弹 DP的相关文章

Laoj P1199 [noip1999]拦截导弹

问题背景 动态规划入门-第18题 试题描述 某国为了防御敌国的导弹袭击,发明出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 现在,要你计算出这套系统最多能拦截多少枚导弹,并且如果要拦截所有导弹的话,最少要配备多少套这种导弹拦截系统. 输入格式 输入数据为两行.第一行为一个整数,表示导弹的数目N.第二行为N个整

NYOJ 79 拦截导弹(dp)

时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发的高度.某天,雷达捕捉到敌国导弹来袭.由于该系统还在试用阶段,所以只用一套系统,因此有可能不能拦截所有的导弹. 输入 第一行输入测试数据组数N(1<=N<=10) 接下来一行输入这组测试数据共有多少个导弹m(1<=m<=20) 接下来行输入导弹依次

拦截导弹(南阳oj)(dp最长下降子序列)

拦截导弹 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发的高度.某天,雷达捕捉到敌国导弹来袭.由于该系统还在试用阶段,所以只用一套系统,因此有可能不能拦截所有的导弹. 输入 第一行输入测试数据组数N(1<=N<=10) 接下来一行输入这组测试数据共有多少个导弹m(1<=m<=20) 接下来行输

codevs1409 拦截导弹2

[问题描述]一场战争正在 A 国与 B 国之间如火如荼的展开.B 国凭借其强大的经济实力开发出了无数的远程攻击导弹,B 国的领导人希望,通过这些导弹直接毁灭 A 国的指挥部,从而取得战斗的胜利!当然,A 国人民不会允许这样的事情发生,所以这个世界上还存在拦截导弹.现在,你是一名 A 国负责导弹拦截的高级助理.B 国的导弹有效的形成了三维立体打击,我们可以将这些导弹的位置抽象三维中间的点(大小忽略),为了简单起见,我们只考虑一个瞬时的状态,即他们静止的状态.拦截导弹设计非常精良,可以精准的引爆对方

1044 拦截导弹

1044 拦截导弹 1999年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 输入描述 Input Description 输入导弹依次飞

百练2945 拦截导弹

描述 某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹.拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹. 输入 输入有两行,第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出

又见拦截导弹

又见拦截导弹 描述 大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.突然有一天,雷达捕捉到敌国的导弹来袭.由于该系统存在缺陷,所以如果想把所有的导弹都拦截下来,就要多准备几套这样的导弹拦截系统.但是由于该系统成本太高,所以为了降低成本,请你计算一下最少需要多少套拦截系统. 输入 有多组测试数据. 每组数据先输入一个整数N(N≤

拦截导弹问题

拦截导弹动态规划问题 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000 的正整数),计算这套系统最多能拦截多少导弹,并依次输出被拦截的导弹飞来时候的高度. 样例: INPUT 389 207 155 300 299 1

tyvj P1209 - 拦截导弹 平面图最小割&amp;&amp;模型转化

P1209 - 拦截导弹 From admin    Normal (OI)总时限:6s    内存限制:128MB    代码长度限制:64KB 背景 Background 实中编程者联盟为了培养技术精湛的后备人才,必须从基础题开始训练. 描述 Description 某国为了防御敌国的导弹袭击,研发出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试验阶段,所以只有