http://acm.hdu.edu.cn/showproblem.php?pid=1501
题意:问第三个串是否能够拆成前2个串,字母顺序不可更改
Sample Input
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
Sample Output
Data set 1: yes
Data set 2: yes
Data set 3: no
记忆化搜索
#include <iostream>
using namespace std;
bool flag, hash[205][205];
int len, len1, len2;
char s[405], s1[205], s2[205];
void dfs (int i, int j, int k) //字符串匹配型深搜,s1[i]和s2[j]分别跟s[k]匹配
{
if (flag)
return ;
if (k == len) //匹配成功
{
flag = true;
return ;
}
if (hash[i][j]) //hash法记忆状态,若状态再次出现则已经不可能匹配成功,记忆化搜索
return ;
hash[i][j] = true;
if (!flag && s1[i] == s[k])
dfs (i+1, j, k+1);
if (!flag && s2[j] == s[k])
dfs (i, j+1, k+1);
}
int main()
{
int t, x = 1;
scanf ("%d", &t);
while (t--)
{
scanf ("%s%s%s", s1, s2, s);
len1 = strlen(s1);
len2 = strlen(s2);
len = strlen(s);
memset (hash, false, sizeof(hash));
flag = false;
dfs (0, 0, 0);
printf ("Data set %d: ", x++);
if (flag)
printf ("yes\n");
else printf ("no\n");
}
return 0;
}
分享到:
相关推荐
杭电hdu acm资料所用杭电的acm题
HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版)
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
hdu_2102_passed_sorce
此程序为hdu的acm2010题,就是解决水仙花数问题
模式识别_hdu_期末复习资料集合_试卷笔记.zip
HDU_ACM_1002_大数相加C源代码,利用字符串处理
数字图像处理_hdu_期末复习资料_试卷等.zip
数字图像处理总ppt_hdu_许老师.pdf
高级计算机图形学_mm的_重点笔记_hdu_吴xy.pdf
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
B_(HDU_1231)(最大子段和,分治).cpp
杭电acm解题报告 详细解析2000-2099 适合acm初学者
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?...
hdu题解的答案十分简单的一个题,思路清晰,特别简单
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
hdu 3378 三国杀标程 解题报告
动态规划DP题解 POJ HDU部分动态规划DP题解
里面包含:实验1~8的源代码,ISE软件直接导入就能使用、课件PPT、3份实验报告、实验要求与评分标准。