POJ 2127 Greatest Common Increasing Subsequence -- 动态规划

题目地址：http://poj.org/problem?id=2127

Description

Input

Output

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;
}

POJ 2127 Greatest Common Increasing Subsequence -- 动态规划,布布扣,bubuko.com

POJ 2127 Greatest Common Increasing Subsequence -- 动态规划

原文：http://blog.csdn.net/jdplus/article/details/20136257