拦截导弹
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
-
某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发的高度。某天,雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段,所以只用一套系统,因此有可能不能拦截所有的导弹。
- 输入
- 第一行输入测试数据组数N(1<=N<=10)
接下来一行输入这组测试数据共有多少个导弹m(1<=m<=20)
接下来行输入导弹依次飞来的高度,所有高度值均是大于0的正整数。 - 输出
- 输出最多能拦截的导弹数目
- 样例输入
-
2 8 389 207 155 300 299 170 158 65 3 88 34 65
- 样例输出
-
6 2
- 来源
- [张洁烽]原创
- 上传者
- 张洁烽
-
1 #include <stdio.h> 2 #include <string.h> 3 long long int s[22]; 4 int longest[22]; 5 int main() 6 { 7 int T; 8 scanf("%d",&T); 9 while(T--) 10 { 11 int i,j,m,max; 12 scanf("%d",&m); 13 for(i=0;i<m;i++) 14 scanf("%d",&s[i]); 15 for(i=0;i<m;i++) 16 longest[i]=1; 17 for(j=1;j<m;j++) 18 { 19 for(i=0;i<j;i++) 20 if(s[j]<s[i]&&(longest[j]<longest[i]+1)) 21 longest[j]=longest[i]+1; 22 } 23 max=longest[0]; 24 for(i=0;i<m;i++) 25 if(longest[i]>max) 26 max=longest[i]; 27 printf("%d ",max); 28 } 29 return 0; 30 }
//最长递减子序列问题,同最长递增子序列问题
//注意这句话“不能高于等于”