题目链接:http://poj.org/problem?id=1887
题目大意:求给定数列到最长不升子序列。关键注意到结果输出完毕后至少要输出1行空行。
代码如下:
#include <cstdio> #include <cstring> using namespace std; const int maxn=40000; int data[maxn]; int dp[maxn]; int max(int a,int b){ return a>b?a:b; } int main(){ int cas; int limit; for(cas=1;;++cas){ int temp=0; scanf("%d",&temp); if(temp==-1)break; data[0]=temp; limit=0; for(int i=1;;++i){ scanf("%d",&temp); if(temp==-1)break; data[i]=temp; limit=i; } dp[0]=1; for(int i=1;i<=limit;++i){ dp[i]=1; for(int j=0;j<i;++j){ if(data[j]>=data[i] && dp[j]+1>dp[i]){ dp[i]=dp[j]+1; } } } int ans=-1; for(int i=0;i<=limit;++i){ ans=max(dp[i],ans); } printf("Test #%d:\n",cas); printf(" maximum possible interceptions: %d\n\n",ans);//这里注意多输出一个或多个空行。 } return 0; }
您还没有登录,请您登录后再发表评论
Pku acm 第1887题 Testing the CATCHER 代码,有详细的注释,动态规划
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
北大POJ3267-The Cow Lexicon
北大POJ2965-The Pilots Brothers' refrigerator 解题报告+AC代码
北大POJ2635-The Embarrassed Cryptographer 解题报告+AC代码
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
北大POJ3267-The Cow Lexicon 解题报告+AC代码
poj 3548 Restoring the digits.md
poj 1611 The Suspects 代码 并查集的应用
poj 3554 Almost the shortest route.md
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
相关推荐
Pku acm 第1887题 Testing the CATCHER 代码,有详细的注释,动态规划
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
北大POJ3267-The Cow Lexicon
北大POJ2965-The Pilots Brothers' refrigerator 解题报告+AC代码
北大POJ2635-The Embarrassed Cryptographer 解题报告+AC代码
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
北大POJ3267-The Cow Lexicon 解题报告+AC代码
poj 3548 Restoring the digits.md
poj 1611 The Suspects 代码 并查集的应用
poj 3554 Almost the shortest route.md
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码