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

 

总结

以上是生活随笔为你收集整理的*【HDU - 5707】Combine String（dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。