首页 > 代码库 > 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 最长上升递增子序列