HDU 1423 Greatest Common Increasing Subsequence

发布时间:2016-12-8 12:19:31 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 1423 Greatest Common Increasing Subsequence",主要涉及到HDU 1423 Greatest Common Increasing Subsequence方面的内容,对于HDU 1423 Greatest Common Increasing Subsequence感兴趣的同学可以参考一下。

即求最长公共自增子序列 题解: 设dp[i][j]表示序列1前i个元素和序列2前j个元素的最长公共递增序列的长度,可以这样进行dp,序列1的前1个元素和序列2的最大所求序列,前2个,3个。。。每一次dp过程记录下最大的值,如果对于某一个第二个序列的元素有a[i]>b[j]且有ma<dp[i-1][j],则更新ma的值,在a[i]==b[j]时ma赋给dp[i][j],过程见代码更易懂 #include <cstdio> #include <cstring> using namespace std; int a[510],b[510],dp[510][510]; int max(int a,int b) { return a>b?a:b; } int main() { int T,n1,n2; scanf("%d",&T); while(T--) { scanf("%d",&n1); for(int i=1;i<=n1;i++) scanf("%d",&a[i]); scanf("%d",&n2); for(int i=1;i<=n2;i++) scanf("%d",&b[i]); memset(dp,0,sizeof(dp)); int ma=0; for(int i=1;i<=n1;i++) { ma=0; for(int j=1;j<=n2;j++) { dp[i][j]=dp[i-1][j]; if(a[i]>b[j]&&dp[i-1][j]>ma)ma=dp[i-1][j]; if(a[i]==b[j])dp[i][j]=ma+1; } } int ans=0; for(int i=1;i<=n1;i++) ans=max(ans,dp[n1][i]); printf("%d\n",ans); if(T!=0) printf("\n"); } return 0; }

上一篇:
下一篇:如何在C#+VS2012环境中使用AutoIt

相关文章

相关评论