ZOJ 2432 Greatest Common Increasing Subsequence（最长公共上升子序列+路径打印）

Greatest Common Increasing Subsequence

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1432

题目大意：给出两串数字，求他们的最长公共上升子序列（LCIS），并且打印出来。

Sample Input

5
1 4 2 5 -12
4
-12 1 2 4

Sample Output

2
1 4

分析：神奇就神奇在是LIS与LCS的组合

令dp[i][j]表示A串的前i个，与B串的前j个，并以B[j]为结尾的LCIS 的长度.

状态转移方程：

　　f(A[i]==B[j]) 　　dp[i][j]=max(dp[i-1][k])+1; ( 1 <= k < j )

　　else 　　dp[i][j]=dp[i-1][j];

然后选择循环顺序，就可以将算法的复杂度降为n*n.

代码如下：

 /*这个代码结果虽然对，跟样例的输出都不一样，而且两个输出数据之间有空行都没有实现，却能AC，有点匪夷所思*/

 # include<stdio.h>

 # include<string.h>

 #define MAX 550

 struct node{

     int x,y;

 }path[MAX][MAX];

 int dp[MAX][MAX];

 int s[MAX],t[MAX];

 int main(){

     int T,i,j;

     scanf("%d",&T);

     while(T--)

     {

         memset(path,,sizeof(path));

         int n,m;

         scanf("%d",&n);

         for(i=; i<=n; i++)

             scanf("%d",&s[i]);

         scanf("%d",&m);

         for(i=; i<=m; i++)

             scanf("%d",&t[i]);

         memset(dp,,sizeof(dp));

         int max = ;

         for(i=; i<=n; i++)

         {

             max = ;

             int tx = ,ty = ;

             for(j=; j<=m; j++)

             {

                 dp[i][j] = dp[i-][j];

                 path[i][j].x = i-;

                 path[i][j].y = j;

                 if( s[i] > t[j] && max < dp[i-][j])

                 {

                     max = dp[i-][j];

                     tx = i-;

                     ty = j;

                 }

                 if( s[i] == t[j] )

                 {

                     dp[i][j] = max+;

                     path[i][j].x = tx;

                     path[i][j].y = ty;

                 }

             }

         }

         max = -;

         int id;

         for(i=; i<=m; i++)

             if(dp[n][i]>max)

             {

                 max = dp[n][i];

                 id = i;

             }

             int save[MAX];

             int cnt=;

             int tx,ty;

             tx=n; ty=id;

             while(dp[tx][ty] !=  )

             {

                 int tmpx,tmpy;

                 tmpx = path[tx][ty].x;

                 tmpy = path[tx][ty].y;

                 if(dp[tx][ty] != dp[tmpx][tmpy])

                 {

                     save[cnt++]=t[ty];

                 }

                 tx = tmpx; ty = tmpy;

             }

             printf("%d\n",max);

             for(i=cnt-; i>=; i--)

                 printf("%d ",save[i]);

             printf("\n");

     }

     return ;

 }

巴特西

ZOJ 2432 Greatest Common Increasing Subsequence（最长公共上升子序列+路径打印）

最新文章

热门文章