简单C程序题目 拦截导弹问题

简单C程序题目 拦截导弹问题

这个问题其实就一个序列
最长的非递增序列。
定义一个状态
以a[i]为最后一个拦截的导弹序列的最长长度。
例如
a[0]=300;
a[1]=207;
a[2]=155;
a[3]=300;
...
我们从头向后看。
以a[0]为最后一个导弹序列的最长长度，和明显就是a[0]自己。也就是1.
以a[1]为最后一个导弹序列的最长长度，因为递减所以就是a[0],a[1],长度为2.
以a[2]为最后一个导弹序列的最长长度，应该前面所有大于a[2]的序列加上1，然后从中取最大的，也就是a[0],a[1],a[2]
下面是程序代码
#include

int main()
{
int m,temp,i=0,j;
int data[100];
int ans[100];
int maxt;
scanf("%d",&m);
temp=m;
while(temp--)
scanf("%d",&data[i++]);
ans[0]=1;
maxt=1;
for(j=1;j {
ans[j]=1;
for(i=0;i {
if(data[i]>=data[j])
{
if(ans[i]+1>ans[j])
ans[j]=ans[i]+1;
}
}

if(ans[j]>maxt)
maxt=ans[j];
}

printf("%d\n",maxt);
}
上面的程序肯定是对的，我以前做过这道题，属于简单的动态规划，
程序已经测试运行过。