Greatest Common Increasing Subsequence
Time Limit:10000MSMemory Limit:65536K
Total Submissions:9762Accepted:2584
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
ac代码
#include<stdio.h>#include<string.h>int n,m;int dp[1010][1010],path[1010][1010],ans[1010],aj,ai,res,a[1010],b[1010];void LCS(){int i,j,mj;res=0;memset(dp,0,sizeof(dp));memset(path,-1,sizeof(path));for(i=1;i<=n;i++){int ma=0;for(j=1;j<=m;j++){dp[i][j]=dp[i-1][j];if(b[j]<a[i]&&dp[i][j]>ma){ma=dp[i][j];mj=j;}else{if(b[j]==a[i]){dp[i][j]=ma+1;path[i][j]=mj;}}if(res<dp[i][j]){res=dp[i][j];ai=i;aj=j;}}}}int main(){while(scanf("%d",&n)!=EOF){int i,j;for(i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);for(j=1;j<=m;j++)scanf("%d",&b[j]);LCS();printf("%d\n",res);int temp=res;while(temp){if(path[ai][aj]>-1){ans[temp–]=b[aj];aj=path[ai][aj];}ai–;}for(i=1;i<=res;i++)printf("%d%c",ans[i],i==res?'\n':' ');}}
，没有了爱的语言，所有的文字都是乏味的
