首页 > 代码库 > hdu 1423 最长上升递增子序列
hdu 1423 最长上升递增子序列
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn=505; 7 int a[maxn],b[maxn],dp[maxn]; 8 9 int main()10 {11 int t,n,m,i,j,k;12 scanf("%d",&t);13 while(t--)14 {15 scanf("%d",&n);16 for(i=1;i<=n;i++) scanf("%d",a+i);17 scanf("%d",&m);18 for(i=1;i<=m;i++) scanf("%d",b+i);19 memset(dp,0,sizeof(dp));20 for(i=1;i<=n;i++)21 {22 k=0;23 for(j=1;j<=m;j++)24 {25 //当前要比较的数值为a[i],所以我们寻找b[j]中比a[i]小,但dp[j]最大的值,找到了就用k记录位置26 if(a[i]>b[j] && dp[j]>dp[k])27 k=j;28 if(a[i]==b[j])//更新最大值29 dp[j]=dp[k]+1;30 }31 }32 int ans=0;33 for(i=1;i<=m;i++)34 ans=max(ans,dp[i]);35 printf("%d\n",ans);36 if(t) puts("");37 }38 return 0;39 }
hdu 1423 最长上升递增子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。