poj 2192 Zipper DP

缘起

日常浪费生命~ poj 2192 Zipper

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给定三个字符串A，B，C；判断C能否由AB中的字符组成，
同时这个组合后的字符顺序必须是A，B中原来的顺序，
不能逆序；例如：A：mnl，B：xyz；如果C为mnxylz，就符合题意；
如果C为mxnzly，就不符合题意，原因是z与y顺序不是B中顺序。

【输入】
多样例. 见样例输入, 单词的长度不超过200

【输出】
见样例输出

【样例输入】
3
cat tree tcraete
cat tree catrtee
cat tree cttaree

【样例输出】
Data set 1: yes
Data set 2: yes
Data set 3: no

【限制】
1s

简单的DP。其实和【1】、【2】非常类似. 令

1
2
3
4
5
dp[i][j]表示a[1,...,i]和b[1,...,j]能否组成c[1,...,i+j]. 则
dp[i][j]=c[i+j]==a[i] && dp[i-1][j] || c[i+j]==b[j] && dp[i][j-1]
最后的答案显然是 dp[n][m]
初始值是 dp[0][0]=true, dp[0][i]=c[1,...,i]和b[1,..,i]是否一样.
dp[i][0]=c[1,..,i]是否和a[1,..,i]一样.

则代码就好写了

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,m;
bool dp[205][205];
char a[205], b[205], c[205];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for (int k = 1;k<=kase; k++)
	{
		memset(dp, 0, sizeof(dp));
		dp[0][0] = true;
		scanf("%s%s%s", a+1,b+1,c+1);
		n = strlen(a+1), m = strlen(b+1);
		for (int i = 1; i<=m; i++)
		{
			dp[0][i] = dp[0][i-1] && b[i] == c[i];
		}
		for (int i = 1; i<=n; i++)
		{
			dp[i][0] = dp[i-1][0] && a[i] == c[i];
		} // dp初始化
		for (int i = 1; i<=n; i++)
		{
			for (int j=  1; j<=m; j++)
			{
				if (c[i+j]!=a[i] && c[i+j]!=b[j]) // c中出现了不在a中也不在b中的字符, 则肯定false啊~
				{
					dp[i][j] = false;
				}
				else // 否则就分情况讨论, 到底c[i+j]是来自a[1,..,i]还是来自b[1,...,j]
				{
					dp[i][j] = c[i+j]==a[i] && dp[i-1][j] || c[i+j]==b[j] && dp[i][j-1];
				}
			}
		}
		printf("Data set %d: ", k);
		dp[n][m]?puts("yes"):puts("no");
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 368kB
Length 999
Lang G++
Submitted 2019-10-05 20:36:29
Shared
RemoteRunId 20930909

参考

【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/

【2】https://yfsyfs.github.io/2019/10/05/poj-3356-AGTC-%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB-%E7%BB%8F%E5%85%B8DP/