*【HDU - 5707】Combine String（dp）

题干：

Given three strings aa, bb and cc, your mission is to check whether cc is the combine string of aa and bb. 
A string cc is said to be the combine string of aa and bb if and only if cc can be broken into two subsequences, when you read them as a string, one equals to aa, and the other equals to bb. 
For example, ``adebcf'' is a combine string of ``abc'' and ``def''. 

Input

Input file contains several test cases (no more than 20). Process to the end of file. 
Each test case contains three strings aa, bb and cc (the length of each string is between 1 and 2000). 

Output

For each test case, print ``Yes'', if cc is a combine string of aa and bb, otherwise print ``No''. 

Sample Input

abc
def
adebcf
abc
def
abecdf

Sample Output

Yes
No

解题报告：

  可以直接bool类型的dp[i][j]代表第一个串前i个和第二个串前j个可否匹配的。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
char a[MAX],b[MAX],c[MAX];
bool dp[2222][2222];
int main()
{
	while(~scanf("%s%s%s",a+1,b+1,c+1)) {
		int la = strlen(a+1);
		int lb = strlen(b+1);
		int lc = strlen(c+1);
		if(la+lb!=lc) {
			puts("No");continue;
		}
		memset(dp,0,sizeof dp);
		dp[0][0]=1;
		for(int i = 1; i<=la; i++) if(c[i] == a[i]) dp[i][0] |= dp[i-1][0];
		for(int i = 1; i<=lb; i++) if(c[i] == b[i]) dp[0][i] |= dp[0][i-1]; 
		for(int i = 1; i<=la; i++) {
			for(int j = 1; j<=lb; j++) {
				if(c[i+j] == a[i]) dp[i][j] |= dp[i-1][j];
				if(c[i+j] == b[j]) dp[i][j] |= dp[i][j-1];
			}
		}
		if(dp[la][lb]) puts("Yes");
		else puts("No");
	}
	return 0 ;
}

但是比赛的时候硬是让我写了个序列自动机+dp。

dp[i][j]代表第一个串前i个和第二个串前j个匹配，需要达到的最小位置。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2000 + 5;
char a[MAX],b[MAX],c[MAX];
int dp[MAX][MAX],trie[MAX][222];
int main()
{
	while(~scanf("%s",a+1)) {		
		scanf("%s",b+1);
		scanf("%s",c+1);
		memset(dp,0x3f,sizeof dp);
		dp[0][0]=0;
		int la = strlen(a+1),lb = strlen(b+1),lc = strlen(c+1); 
		if(la+lb!=lc) {
			puts("No");continue;
		}
		for(int i = 0; i<=129; i++) trie[lc+1][i]=trie[lc+2][i] = lc+1;
		for(int i = lc; i>=1; i--) {
			int cur = c[i] ;
			for(int j = 0; j<129; j++) {
				if(j == cur) trie[i][j] = i;
				else trie[i][j] = trie[i+1][j];
			}
		}
		for(int i = 1; i<=la; i++) dp[i][0] = trie[dp[i-1][0]+1][a[i]];
		for(int i = 1; i<=lb; i++) dp[0][i] = trie[dp[0][i-1]+1][b[i]];
		for(int i = 1; i<=la; i++) {
			for(int j = 1; j<=lb; j++) {
				dp[i][j] = min(dp[i][j],trie[dp[i-1][j]+1][a[i]]);
				dp[i][j] = min(dp[i][j],trie[dp[i][j-1]+1][b[j]]);
			}
		}
		if(dp[la][lb] != lc) puts("No");
		else puts("Yes");
	}


	return 0 ;
}