1. 题目源地址：http://poj.org/problem?id=1887
2. 易错点：题目倒不是很难，利用DP求最长非递增子序列，其实和DP求最长递增子序列是差不多的。
易错点在于数组要开的足够大，之前开200,2000都不行，后来开到5000才AC了。
关于DP求最长递增子序列之前写过一篇博客的，这里附上链接：http://blog.csdn.net/u012856866/article/details/38901399
3. 解题代码：
//POJ--1887:Testing the CATCHER DP求最长非递增子序列
#include<iostream>
using namespace std;
int main()
{
int num[5000],dp[5000];
int n,i,j;
int caseNum=0;
while(cin>>num[0] && num[0]!=-1)
{
caseNum++;
for(n=1; ;n++)
{
cin>>num[n];
if(num[n]==-1)
break;
}
for(i=0;i<n;i++)
dp[i]=1;
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(num[j]>=num[i] && dp[j]+1>dp[i])//注意和DP求最长递增子序列的区别
dp[i]=dp[j]+1;
}
}
int max=0;
for(i=0;i<n;i++)
{
if(dp[i]>max)
max=dp[i];
}
cout<<"Test #"<<caseNum<<":"<<endl;
cout<<" maximum possible interceptions: "<<max<<endl;
cout<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163028.html
