题目含义
找两个序列共有的, 单调递增的, 最大的子序列
题目分析
两个长序列的情况, 可以由两个短的序列发展而来, 也就是可以用动态分析
令 dp[i][j] 表示第一条序列到 ai, 第二条序列到 bj, 同时 bj 是公共子序列的最后一项时的公共子序列长度
如果 a[i]!=b[j], 那么 dp[i][j]=dp[i-1][j]
如果 a[i]==b[j], 那么 dp[i][j]=max(dp[i-1][k])+1,0<=k<j
而这个 k 在哪取呢, 就是在上一次 a[i]==b[j] 时的 j 了
每次遇到 a[i]==b[j] 时, 给它赋上前一个点的位置, 这样就可以递归找到子序列了
题目代码
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- #include<algorithm>
- using namespace std;
- typedef long long LL;
- const int maxn=507;
- LL a[maxn],b[maxn];
- int t,n,m,dp[maxn][maxn];
- struct node{
- int x,y;
- }path[maxn][maxn];
- int main(){
- scanf("%d",&t);
- while(t--){
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%lld",&a[i]);
- scanf("%d",&m);
- for(int i=1;i<=m;i++)
- scanf("%lld",&b[i]);
- for(int i=1;i<=n;i++){
- int mx=0,tx=0,ty=0;
- for(int j=1;j<=m;j++){
- dp[i][j]=dp[i-1][j];
- path[i][j].x=i-1;
- path[i][j].y=j;
- if(a[i]==b[j]){
- dp[i][j]=mx+1;
- path[i][j].x=tx;
- path[i][j].y=ty;
- }
- if(dp[i-1][j]>mx&&a[i]>b[j]){
- mx=dp[i-1][j];
- tx=i;
- ty=j;
- }
- }
- }
- int mx=0,tx=n,ty;
- for(int i=1;i<=m;i++)
- if(dp[n][i]>mx){
- mx=dp[n][i];
- ty=i;
- }
- int save[maxn],cnt=0;
- while(dp[tx][ty]!=0){
- int tempx=path[tx][ty].x;
- int tempy=path[tx][ty].y;
- if(dp[tx][ty]!=dp[tempx][tempy])
- save[++cnt]=b[ty];
- tx=tempx;
- ty=tempy;
- }
- printf("%d\n",mx);
- for(int i=cnt;i>0;i--)
- printf("%d",save[i]);
- printf("\n");
- if(t)printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3131339.html