//导弹，求最长下降子序列长度，注意输出，1PE，o(╯□╰)o
#include<iostream>
using namespace std;
#define M 5000
int height[M+1];
int maxlen[M+1];
int dp(int n)
{
int i,j,tmp;
maxlen[0]=1;
for(i=1;i<n;i++)
{
tmp=0;
for(j=0;j<i;j++)
if(height[i]<height[j] && maxlen[j]>tmp)
tmp=maxlen[j];
maxlen[i]=tmp+1;
}
tmp=1;
for(i=0;i<n;i++)
if(maxlen[i]>tmp)
tmp=maxlen[i];
return tmp;
}
int main()
{
int k,n,t;
k=1;
n=0;
while(scanf("%d",&t)==1 )
{
if(t==-1 )
{
if(n==0) return 0;
else {
printf("Test #%d:\n maximum possible interceptions: %d\n\n",k,dp(n));
memset(height,0,sizeof(height));
memset(maxlen,0,sizeof(maxlen));
n=0;
k++;
}
} else height[n++]=t;
}
return 0;
}posted on 2009-05-23 18:35
wyiu 阅读(70)
评论(0) 编辑 收藏 引用 所属分类:
POJ