题目地址：http://poj.org/problem?id=2127
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 , . . . , SN of length N is called an increasing subsequence of a sequence A1 , A2 , . . . , AM of length M if there exist 1 <= i1 < i2 < . . . < iN
<= M such that Sj = Aij for all 1 <= j <= N , and Sj < Sj+1 for all 1 <= j < N .
Sequence S1 , S2 , . . . , SN of length N is called an increasing subsequence of a sequence A1 , A2 , . . . , AM of length M if there exist 1 <= i1 < i2 < . . . < iN
<= M such that Sj = Aij for all 1 <= j <= N , and Sj < Sj+1 for 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.
them.
Sample Input
5
1 4 2 5 -12
4
-12 1 2 4
Sample Output
2
1 4
状态dp[i][j]表示seq1[i]从1到i与seq2[j]从1到j并以j为结尾的LCIS的长度
状态转移方程：
dp[i][j] = max(dp[i][k]) + 1, if seq1[i] ==seq2[j], 1 <= k < j
dp[i][j] = dp[i-1][j], if seq1[i] != seq2[j]
#include <stdio.h>
#include <string.h> #define MAX 501 typedef struct path{
int x, y;
}Pre; int seq1[MAX], seq2[MAX];
int len1, len2;
int dp[MAX][MAX]; //状态dp[i][j]记录seq1前i个与seq2前j个并以seq2[j]为结尾的LCIS的长度
Pre pre[MAX][MAX];//pre[i][j]记录前驱
int path[MAX];//根据pre[i][j]回溯可得到LCIS
int index; int LCIS(){
int i, j;
int max, tx, ty;
int id_x, id_y;
int tmpx, tmpy;
//给dp[i][j]、pre[i][j]置初值
memset(dp, 0, sizeof(dp));
memset(pre, 0, sizeof(pre));
for (i = 1; i <= len1; ++i){
max = 0;
tx = ty = 0;
for (j = 1; j <= len2; ++j){
//状态转移方程
dp[i][j] = dp[i-1][j];
pre[i][j].x = i - 1;
pre[i][j].y = j;
if (seq1[i] > seq2[j] && max < dp[i-1][j]){
max = dp[i-1][j];
tx = i - 1;
ty = j;
}
if (seq1[i] == seq2[j]){
dp[i][j] = max + 1;
pre[i][j].x = tx;
pre[i][j].y = ty;
}
}
}
//找到LCIS最后的数字的位置
max = -1;
for (i = 1; i <= len2; ++i){
if (dp[len1][i] > max){
max = dp[len1][i];
id_y = i;
}
}
id_x = len1;
index = 0;
while (dp[id_x][id_y] != 0){
tmpx = pre[id_x][id_y].x;
tmpy = pre[id_x][id_y].y;
//若找到前一对公共点，则添加进路径
if (dp[tmpx][tmpy] != dp[id_x][id_y]){
path[index] = seq2[id_y];
++index;
}
id_x = tmpx;
id_y = tmpy;
}
return max;
} int main(void){
int i;
while (scanf("%d", &len1) != EOF){
for (i = 1; i <= len1; ++i)
scanf("%d", &seq1[i]);
scanf("%d", &len2);
for (i = 1; i <= len2; ++i)
scanf("%d", &seq2[i]); printf("%d\n", LCIS());
--index;
if (index >= 0)
printf("%d", path[index]);
for (i = index - 1; i >= 0; --i){
printf(" %d", path[i]);
}
printf("\n");
} return 0;
}