Greatest Common Increasing Subsequence
Time Limit:10000MSMemory Limit:65536K
Total Submissions:10340Accepted:2727
Case Time Limit:2000MSSpecial Judge
Description
You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length.Sequence S1, S2, . . . , SNof length N is called an increasing subsequence of a sequence A1, A2, . . . , AMof length M if there exist 1 <= i1< i2< . . . < iN<= M such that Sj= Aijfor all 1 <= j <= N , and Sj< Sj+1for all 1 <= j < N .
Input
Each sequence is described with M — its length (1 <= M <= 500) and M integer numbers Ai(-231<= Ai< 231) — the sequence itself.
Output
On the first line of the output file print L — the length of the greatest common increasing subsequence of both sequences. On the second line print the subsequence itself. If there are several possible answers, output any of them.
Sample Input
51 4 2 5 -124-12 1 2 4
Sample Output
21 4
Source
, Northern Subregion
链接：?id=2127
思路：也是一道模板题，，求最长递增公共子序列，并记录路径返回输出；
状态：dp[i][j]表示以s1串的前i个字符s2串的前j个字符且以s2[j]为结尾构成的LCIS的长度。
状态转移：当 s1[i-1]!=s2[j-1]时,按照lcs可知由2个状态转移过来,dp[i-1][j],dp[i][j-1],因为dp[i][j]是以s2[j]为结尾构成的LCIS的长度。所以s2[j-1]一定会包含在里面，所以舍去dp[i][j-1],只由dp[i-1][j] 转移过来。
当s1[i-1]==s2[j-1]，这时肯定要找前面s1[ii-1]==s2[jj-1]的最长且比s2[j-1]小的状态转移过来.若s1[i-1]!=s2[j-1] 那么dp[i][j]=dp[i][j-1]若s1[i-1]==s2[j-1] 那么dp[i][j]=MAX{dp[i-1][k]+1(0<k<j),s2[k-1]<s2[j-1]};
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int n,m,a[505],b[505];int dp[505][505];int rd[505][505];void LICS(){int ans=0; // int dp[505]={0};int mac=0;//用来记录路径的中间变量int I,J;//最后的坐标int lu[505];//用来最后输出路径for(int i=1;i<=n;i++){int len=0; //长度for(int j=1;j<=m;j++){int k=dp[i][j]=dp[i-1][j];if(len<k && a[i]>b[j]){len=k;//记录相等前小于a[i]的最大长度mac=j;}if(a[i]==b[j]){dp[i][j]=len+1;rd[i][j]=mac;//记录最大长度下，上一个j的坐标}if(ans<dp[i][j])//更新最大长度，并记录结尾的坐标{ans=dp[i][j];I=i;J=j;}}}/* printf("(%d,%d)\n",I,J);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d ",rd[i][j]);}printf("\n");}*/printf("%d\n",ans);int Len=ans;if(Len>0){lu[Len–]=J;}while(Len && I && J){ //printf("(%d,%d),rd=%d\n",I,J,rd[I][J]);if(rd[I][J]>0){lu[Len–]=rd[I][J];J=rd[I][J];}I–;}for(int i=1;i<=ans;i++){printf("%d ",b[lu[i]]);}printf("\n");}int main(){while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++){scanf("%d",&a[i]);}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d",&b[i]);}LICS();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
或许人生就是一场旅行，在旅行中遇到的每一个人，
