首页 > 代码库 > hdu 1501 Zipper（DP）
hdu 1501 Zipper（DP）
题意：
给三个字符串str1、str2、str3
问str1和str2能否拼接成str3。（拼接的意思可以互相穿插）
能输出YES否则输出NO。
思路：
如果str3是由str1和str2拼接而成，str1的前i个字符和str2的前j个字符一定构成str3的前i+j个字符。（因为拼接必须保证字符的顺序不变）
所以，，，这算是个变形的最长公共子序列？
DP方程：dp[i][j]：str3的前i+j个字符能否由str1的前i个字符和str2的前j个字符拼接而成。布尔型。
看代码，，
代码：
char s1[205], s2[205], s3[505];bool dp[205][205];int main(){ int T; cin>>T; rep(t,1,T){ scanf("%s%s%s",s1,s2,s3); int l1=strlen(s1); int l2=strlen(s2); int l3=strlen(s3); mem(dp,false); dp[0][0]=true; rep(i,1,l1){ dp[i][0]=(dp[i-1][0]&&(s1[i-1]==s3[i-1])); } rep(i,1,l2){ dp[0][i]=(dp[0][i-1]&&(s2[i-1]==s3[i-1])); } rep(i,1,l1){ rep(j,1,l2){ if(s1[i-1]==s3[i+j-1]){ dp[i][j]=(dp[i][j] || dp[i-1][j]); } if(s2[j-1]==s3[i+j-1]){ dp[i][j]=(dp[i][j] || dp[i][j-1]); } } } if(dp[l1][l2]){ printf("Data set %d: yes\n",t); }else{ printf("Data set %d: no\n",t); } } return 0;}
hdu 1501 Zipper（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。