NYOJ 79

  1. 云栖社区>
  2. 博客>
  3. 正文

NYOJ 79

哈沙给 2012-04-22 11:10:00 浏览320
展开阅读全文

 

 拦截导弹

时间限制: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

 

 

 

 

//AC

#include<stdio.h>

#define N 21

int dp(int b[],int n)

{

int i,j;int max;int d[N];

for(i=0;i<N;i++)

d[i]=1;

for(i=n-2;i>=0;i--)

for(j=i+1;j<=n-1;j++)

if(b[j]<b[i]&&d[i]<d[j]+1)

d[i]=d[j]+1;

max=d[0];

for(i=1;i<n;i++)

{

if(max<d[i])

max=d[i];

}

return max;

}

int main()

{

int i,j,num;int T,ans;

int a[N];

scanf("%d",&T);

for(i=1;i<=T;i++)

{

scanf("%d",&num);

for(j=0;j<num;j++)

scanf("%d",&a[j]);

ans=dp(a,num);

printf("%d\n",ans);

}

return 0;

}

 

 

 

 

 

 

 

 

 

        

 

 

 

 

 

 

//还不太动为啥错

#include<stdio.h>

#define N 21

int dp(int b[],int n)

{

int i,j,k;int max;int d[N];

for(i=0;i<N;i++)

d[i]=1;

for(i=0;i<n-1;i--)

{

k=i;

for(j=i+1;j<n;j++)

if(b[j]<b[k])

{

d[i]++;

k++;

}

else

break;

 

}

max=d[0];

for(i=1;i<n;i++)

{

if(max<d[i])

max=d[i];

}

return max;

}

int main()

{

int i,j;int T,ans,num;

int a[N];

scanf("%d",&T);

for(i=1;i<=T;i++)

{

scanf("%d",&num);

for(j=0;j<num;j++)

scanf("%d",&a[j]);

ans=dp(a,num);

printf("%d\n",ans);

}

return 0;

}

 

 

//实参和形参不匹配,程序也会停止

 //无符号十进制为%U

 

 

 

 

 

网友评论

登录后评论
0/500
评论
哈沙给
+ 关注