poj 1887 最长下降子序列

dp，和求 LIS一样

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int maxn=100005;int dp[maxn],a[maxn];int main(){int n;int cas=0;while(scanf("%d",&a[0])&&a[0]!=-1){n=0;while(a[n]!=-1)scanf("%d",&a[++n]);int ans=-1;for(int i=0;i<n;i++){dp[i]=1;for(int j=i-1;j>=0;j--)if(a[i]<a[j]&&dp[j]+1>dp[i])dp[i]=dp[j]+1;if(ans<dp[i])ans=dp[i];}if(cas)puts("");printf("Test #%d:\n",++cas);printf("  maximum possible interceptions: %d\n",ans);}}