HDU-1503 Advanced Fruits题解

题目大意

给你两个字符串，问你如何按照顺序，将两个字符串合并后，输出最短的和字符串。

解题思路

本来我是想到，用LCS求出最短字符串后，用第二个字符串删去最长公共子序列，但是WA了。。。

后来查了题解才发现，应该顺序不能变。

那么这题就是一个LCS的应用，记录路径，倒序递归输出。

（明明是LCS，我也学了，但是就是写不出。。哎，还需要努力）

不是很熟悉LCS的话，可以参考以下这张图。

很清楚的展示了路径。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
struct {
	int val;
	int mark;//记录状态
}dp[N][N];
char a[N], b[N];

void P(int i ,int j) {
	if (i + j == 0)	return;
	if (dp[i][j].mark == 0) {
		P(i-1, j-1);
		cout << a[i];
	}
	else if (dp[i][j].mark == 1) {	
		P(i-1, j);
		cout << a[i];
	}
	else {
		P(i, j-1);
		cout << b[j];
	}
}

int main() {
	int n, m;
	while (cin >> a + 1 >> b + 1) {
		n = strlen(a + 1);
		m = strlen(b + 1);
		for (int i = 1; i <= n; i++) {
			dp[i][0].mark = 1;
			for (int j = 1; j <= m; j++) {
				dp[0][j].mark = -1;
				dp[i][j].mark = 0;
				if (dp[i - 1][j].val > dp[i][j - 1].val) {
					dp[i][j].mark = 1;
				}
				else dp[i][j].mark = -1;
				dp[i][j].val = max(dp[i - 1][j].val, dp[i][j - 1].val);
				if (a[i] == b[j]) {
					if (dp[i - 1][j - 1].val + 1 > dp[i][j].val) {
						dp[i][j].mark = 0;
					}
					dp[i][j].val = max(dp[i][j].val, dp[i - 1][j - 1].val + 1);
				}
			}
		}
		P(n, m);
		cout << endl;
	}
}