hdu 1503 Advanced Fruits LCS dp

缘起

【1】中是LCS（最长公共子序列的板题），本题 在【1】的基础上要打印出最优方案.

分析

题意很裸的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
“21世纪水果”公司专注于通过将基因从一种水果转移到另一种水果的基因组中来创造新的水果。大多数情况下，这种
方法不起作用，但有时候，在非常罕见的情况下，会出现一种新的水果，它们的味道就像两者之间的混合物。
公司内部讨论的一个重要话题是“如何给新的杂交品种命名？” 苹果和梨之间的混合物当然可以称为苹果梨，但这听起来并不是很有趣。老板最终决定使用包含原始水果名称的最短字符串作为子字符串作为新名称。例如，“applear”包
含“apple”和“pear”（APPLEar和apPlEAR），并且没有具有相同属性的更短字符串。

因此，蔓越莓和波森莓的组合将被称为“boysecranberry”或“craboysenberry”。

你的工作是编写一个程序，为两个给定水果的组合计算这么短的名字。您的算法应该是高效的，否则它不太可能在分
配时间长的水果名称中执行。

【输入】
输入的每一行包含两个字符串，表示应组合的水果的名称。 所有名称的最大长度均为100，并且仅包含字母字符。
输入由文件结束终止。

【输出】
对于每个测试用例，在一行上输出结果水果的最短名称。 如果可能有多个最短名称，则任何一个都是可接受的。

【样例输入】
apple peach
ananas banana
pear peach

【样例输出】
appleach
bananas
pearch

【限制】
Time limit 1000 ms
Memory limit 32768 kB
接受special judge

显然就是要求出两个水果中的 LCS， 并且输出最优方案（可能不止一个，但是任何一个都是可以的）

算法如下图

其实我们在dp的过程中要记录每个节点是怎么来的. 于是就画出了上面的图. 则我们就可以从 dp[lenx-1][leny-1]按图索骥回到dp[0][0], 则这一路上, 如果是斜着的, 则就是公共字符，如果是水平的，则就是徒增y, x没动, 则就是写入y的字符，如果是垂直的，则就是徒增x, y没动，则就是写入x的字符. 于是写出的字符就是想要的杂交品种的名称的倒序. 则逆序输出就是答案. 其实你想想是很合理的——如果上面的从dp[0][0] 到 dp[lenx-1][leny-1] 不允许出现斜线的话——仅仅允许垂直和水平，则折线的长度就是lenx+leny, 但是由于斜线的存在——节省了一个字符. 节省的字符就是公共字符.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>

//#define LOCAL

const int MAX_N = 105;
char x[MAX_N], y[MAX_N], ans[MAX_N<<1];
int lenx, leny, top;
struct
{
	int v,h,len; // dp[i][j]的状态是从dp[i-v][j-h]来的, dp[i][j] = len, 表示x[1,...,i] 和 y[1,...,j]的LCS是len, 1<=i<=lenx, 1<=j<=leny, v是到达本状态前一步垂直方向移动的距离(即纵坐标的变动), h是到达本状态前一步水平方向移动的距离(即横坐标的变动)
}dp[MAX_N][MAX_N];

int main(void)
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	dp[0][0].len = 0;
	for (int i = 1; i<MAX_N; i++) // 确定 dp[i][0], 即水平底边
	{
		dp[i][0].len = 0; // 因为y序列是空序列,所以恒为0
		// 边界上的点只能从边界上来
		dp[i][0].v = 0; // 垂直走0
		dp[i][0].h = 1; // 水平走1,即i坐标的变动
	}
	for (int i = 1; i<MAX_N; i++) // 确定 dp[0][i], 即垂直侧边
	{
		dp[0][i].len = 0; // 因为x序列是空序列,所以恒为0
		// 边界上的点只能从边界上来
		dp[0][i].h = 0; // 水平不动
		dp[0][i].v = 1; // 垂直走1, 即j坐标的变动
	} // 初始化完毕
	while(~scanf("%s%s", x+1, y+1))
	{
		lenx = strlen(x+1), leny = strlen(y+1);
		// 至此, 初始化完成
		for (int i = 1; i<=lenx;i++) // 开始dp
		{
			for (int j = 1; j<=leny;j++)
			{
				if (x[i]==y[j]) // dp[i][j]是从dp[i-1][j-1]转移来的.
				{
					dp[i][j].len = dp[i-1][j-1].len+1;
					dp[i][j].v = dp[i][j].h = 1;
				}
				else
				{
					if (dp[i-1][j].len > dp[i][j-1].len)
					{
						dp[i][j].len = dp[i-1][j].len; // dp[i][j]是从dp[i-1][j]来的
						dp[i][j].v = 0; // 垂直不动
						dp[i][j].h = 1; // 水平移动1
					}
					else
					{
						dp[i][j].len = dp[i][j-1].len; // dp[i][j]是从dp[i][j-1]来的
						dp[i][j].v = 1; // 垂直移动1
						dp[i][j].h = 0; // 水平不动
					}
				}
			}
		}
		// 至此 dp 完毕, 就要开始求解了——按图索骥或者说是顺藤摸瓜——从dp[lenx][leny]往回搜索
		top = 0;
		int i1 = lenx, j = leny;
		while(i1||j) // 只要还没回到 dp[0][0]
		{
			int dv = dp[i1][j].v, dh = dp[i1][j].h;
			if (dp[i1][j].v && dp[i1][j].h) // 如果是从 dp[i-1][j-1]到达的dp[i][j]
			{
				ans[top++] = x[i1];
			}
			else if (dp[i1][j].v) // 如果是从dp[i][j-1]到达dp[i][j]
			{
				ans[top++] = y[j];
			}
			else // 如果是从dp[i-1][j] 到达 dp[i][j]
			{
				ans[top++] = x[i1];
			}
			i1-=dh;
			j-=dv;
		} // 最后i和j都变成0了
		for (int i = top-1; ~i; i--)
		{
			putchar(ans[i]);
		}
		puts("");
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 1852kB
Length 2087
Lang C++
Submitted 2019-07-29 14:10:32
Shared
RemoteRunId 29960666

参考

【1】https://yfsyfs.github.io/2019/07/28/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97%EF%BC%88LCS%EF%BC%89%E9%97%AE%E9%A2%98-hdu-1243-%E5%8F%8D%E6%81%90%E8%AE%AD%E7%BB%83%E8%90%A5/#more