`
yiheng
  • 浏览: 155691 次
社区版块
存档分类

poj 2192 记忆化&dfs

    博客分类:
  • DP
DP 
阅读更多

给三个串,问 第三个串能否 由前两个串构成。。

dfs+剪枝。。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=210;
char sa[maxn],sb[maxn],p[maxn<<1];
//int dp[maxn][maxn];
int lena,lenb,lenp;

bool dfs(int la,int lb,int lp){
	if(la==lena&&lb==lenb)return true;
	if(la<lena&&sa[la]==p[lp]){
		if(dfs(la+1,lb,lp+1))return true;
	}
	if(lb<lenb&&sb[lb]==p[lp]){
		if(dfs(la,lb+1,lp+1))return true;
	}
	return false;
}

int main(){
	int t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++){
		scanf("%s%s%s",sa,sb,p);
		lena=strlen(sa);
		lenb=strlen(sb);
		lenp=strlen(p);
		printf("Data set %d: ",cas);
		if(lena+lenb!=lenp || sa[lena-1]!=p[lenp-1]&&sb[lenb-1]!=p[lenp-1]){puts("no");continue;}
		bool OK=dfs(0,0,0);
		if(OK)puts("yes");
		else puts("no");
	}
}

dp  记忆化 。。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=210;
char sa[maxn],sb[maxn],p[maxn<<1];
int dp[maxn][maxn];
int lena,lenb,lenp;

bool funDP(int i,int j){
	if(dp[i][j]!=-1)return dp[i][j];
	if(i==0&&j==0)return dp[i][j]=true;
	if(i>0&&sa[i]==p[i+j])if(funDP(i-1,j))return dp[i][j]=true;
	if(j>0&&sb[j]==p[i+j])if(funDP(i,j-1))return dp[i][j]=true;
	return dp[i][j]=false;
}

int main(){
	int t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++){
		scanf("%s%s%s",sa+1,sb+1,p+1);
		lena=strlen(sa+1);
		lenb=strlen(sb+1);
		lenp=strlen(p+1);
		//printf("%d %d %d\n",lena,lenb,lenp);
		printf("Data set %d: ",cas);
		if(lena+lenb!=lenp || sa[lena]!=p[lenp]&&sb[lenb]!=p[lenp]){puts("no");continue;}
		memset(dp,-1,sizeof(dp));
		bool OK=funDP(lena,lenb);
		if(OK)puts("yes");
		else puts("no");
	}
}



分享到:
评论

相关推荐

    POJ1696-Space Ant

    4. **记忆化或动态规划**:如果问题规模较大,可能需要使用记忆化搜索或动态规划来降低时间复杂度,避免重复计算。 5. **数据结构**:可能需要用到链表、栈或队列等数据结构来辅助实现DFS。 6. **边界条件和特殊...

    acm poj300题分层训练

    5. **搜索算法的优化**:poj1699、poj3411等训练搜索技巧和剪枝方法,poj3373、poj1691则介绍了记忆化搜索。 6. **更复杂的动态规划**:poj1191、poj1054等题目增加了动态规划的难度,引入了记录状态的DP和树型DP。 ...

    北大POJ初级-图算法

    通过分析这些代码,你可以看到算法的具体实现,包括数据结构的选择(如栈、队列、优先队列)、递归或迭代的策略,以及优化技巧,如记忆化搜索或动态规划。 学习和实践这些图算法不仅有助于提高在POJ等在线判题系统...

    POJ 1077 算法

    为了提高效率,可以采用记忆化搜索或者剪枝策略来避免重复计算和无效搜索。 解决这个问题的过程中,还需要掌握动态规划、递归、回溯等算法思想,并理解如何有效地利用C++的容器(如栈、队列)和算法库(如STL)来...

    ACM-POJ 算法训练指南

    2. **记忆化搜索**:结合动态规划和递归搜索(POJ3254, poj2411, poj1185)。 3. **多维动态规划**:处理多个维度的状态(poj2057, poj1947, poj2486, poj3140)。 ### 十五、进阶数学 1. **数列和级数**:数列...

    poj上算法题目分类

    - **记忆化搜索**:通过存储中间结果避免重复计算。 ### 2. Dijkstra 算法 Dijkstra 算法是一种用于求解单源最短路径问题的贪心算法,适用于无负权边的加权图。 **示例题目编号:** - 1022, 1111, 1118, 1129, ...

    POJ ACM 的题目分类

    - **动态规划**(如1088, 2348, 2413等题目):这类问题通常要求通过递推关系求解最优化问题,需要理解状态转移方程并设计合适的记忆化或自底向上的策略。 - **贪心算法**(如1037, 1970等):贪心算法是每次做出...

    02.北大POJ题库使用指南.docx

    2. **动态规划(DP)与记忆化搜索**: 动态规划是解决具有重叠子问题和最优子结构特征的问题的有效方法,如背包问题、最长公共子序列等。记忆化搜索是动态规划的一种优化,用于避免重复计算。如1037、1125、1458等...

    参加ACM大赛应该准备哪些课程? (2).pdf

    3. 动态规划的各个典型(LCS、最长递增子串、三角剖分、记忆化dp) 4. 博弈类算法(博弈树、二进制法) 5. 双向广度搜索、A*算法、最小耗散优先 6. 差分约束系统 7. Hash表 图论 1. 网络流问题 2. 最小费用流 3. ...

    ACM算法总结大全——超有用!.pdf

    5. **搜索**:最优化剪枝、搜索技巧和优化、记忆化搜索。 6. **动态规划**:处理更复杂的问题,如动态规划解施行商问题等。 这份总结大全涵盖了ACM竞赛所需的基础知识和进阶技能,是学习算法和数据结构的好资源。...

    ACM训练方案

    5. 搜索优化:最优化剪枝、搜索技巧和记忆化搜索。 这些内容构成了一个全面的ACM训练框架,旨在全面提升参赛者的编程思维、算法实现和问题解决能力。通过不断练习和深入理解,参赛者可以逐步提高在ACM竞赛中的表现...

    算法竞赛专题解析--搜索进阶(2)剪枝1

    文章提到了不同类型的剪枝方法,包括BFS的判重剪枝、DFS的各种剪枝技术,如可行性剪枝、最优性剪枝、搜索顺序剪枝、排除等效冗余和记忆化搜索。 1. BFS的剪枝通常基于状态的重复性,如八数码问题中,通过记录和比较...

    搜索专题

    - **记忆化搜索**:虽然本例中没有直接使用记忆化搜索,但在复杂问题中使用记忆化搜索可以有效避免重复计算,提高效率。 #### 2. **动态规划(DP)** - **概念**:动态规划是一种通过将问题分解为互相重叠的子...

    常用算法 (2).pdf

    7. **动态规划**:LCS(最长公共子序列)、最长递增子串、三角剖分、记忆化DP等。 8. **博弈类算法**:博弈树、二进制搜索等。 9. **最大团和最大独立集**:寻找图中最大规模的完全子图和没有边相连的顶点集合。 10....

    常用计算机算法列表.pdf

    动态规划和记忆化搜索是优化问题求解的有效策略,适用于背包问题、最长子序列等问题。 在编程竞赛中,掌握C++标准模板库(STL)的使用、图算法、数据结构和排序算法(如快速排序、堆排序)至关重要。例如,poj题目...

    北京大学-动态规划-讲解PDF

    动态规划也可以理解为带有记忆化的搜索,即它是一种自底向上的方法,而不是递归地从上到下解决问题。 文档还通过一个具体的实例——POJ1163数字三角形问题来演示动态规划的工作方式。在这个问题中,需要在数字构成...

    -ACM培训资料

    5. **动态规划**:包括LCS(最长公共子序列)、最长递增子串、三角剖分、记忆化DP等经典问题。 6. **博弈类算法**:如博弈树和二进制搜索,解决博弈问题。 7. **最大团和最大独立集**:图论中的问题,寻找最大的完全...

    算法之路 ,成功掌握各种算法

    - **动态规划**:解决如LCS(最长公共子序列)、记忆化搜索等问题。 - **博弈算法**:如博弈树分析等。 - **最大团、最大独立集**:图论中的经典问题。 - **差分约束系统**:用于解决一些优化问题。 ##### 2. 计算...

Global site tag (gtag.js) - Google Analytics