hdu 5707 Combine String

xiaoxiao2021-02-28  50

Combine String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 2945    Accepted Submission(s): 823 Problem Description Given three strings  a b and  c, your mission is to check whether  c is the combine string of  a and  b. A string  c is said to be the combine string of  a and  b if and only if  c can be broken into two subsequences, when you read them as a string, one equals to  a, and the other equals to  b. 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  a b and  c (the length of each string is between 1 and 2000).   Output For each test case, print ``Yes'', if  c is a combine string of  a and  b, otherwise print ``No''.   Sample Input abc def adebcf abc def abecdf   Sample Output Yes No   Source "巴卡斯杯" 中国大学生程序设计竞赛 - 女生专场    Recommend liuyiding   Statistic |  Submit |  Discuss |  Note

这题的意思是s1和s2字符串能否拼接成s3字符串,s1和s2内的字符相对位子不能打乱

这题刚开始做的时候感觉是动态规划,但是又推不出动态规划的转化公式,后来看了别人写的题解,发现这题很巧妙

其实这题就像是最长公共子序列(LCS)

转化方程为

s1[i]==s3[I+j].    则dp[i][j]=max(dp[i][j],dp[i-1][j])

s2[j]==s3[I+j].   则dp[i][j]=max(dp[i][j],dp[i][j-1])

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s1[2005],s2[2005],s3[2005]; int v[2005][2005]; int main() { while (scanf("%s",s1+1)!=EOF) { scanf("%s%s",s2+1,s3+1); memset(v, 0, sizeof(v)); v[0][0]=1; int t1=int(strlen(s1+1)),t2=int(strlen(s2+1)); if((t1+t2)!=strlen(s3+1)){ printf("No\n"); continue; } for(int i=0;i<=t1;i++) for (int j=0; j<=t2; j++) { if(i>0&&s1[i]==s3[i+j]) v[i][j]=max(v[i-1][j],v[i][j]); if(j>0&&s2[j]==s3[i+j]) v[i][j]=max(v[i][j-1],v[i][j]); } if(v[t1][t2]) printf("Yes\n"); else printf("No\n"); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-2300047.html

最新回复(0)