现在的位置: 首页 > 综合 > 正文

hdu1501-poj2192详细解题报告

2017年02月22日 ⁄ 综合 ⁄ 共 1492字 ⁄ 字号 评论关闭

第一眼看到这个题目就想到用字符串模拟....自己嫩得跟什么似得.....后面问了学长...自己想了很久,然后这里给出详细结题报告:个人觉得这个对于刚接触 dp 的人来说是一个比较好的经典题目,很有dp的思维(对于目前菜菜的我来说)

题意:给你三个字符串,A、B、C,问你A和B能否组成C,当然是有要求的,那就是所有组成C的字母一定要按照A和B的顺序来,不能乱,意思就是从C中按顺序把组成A(或B)的所有字母拿出来,剩下的就是B(或A)

分析:首先给出详细分析如何得到dp状态转移方程,然后就是详细的实现过程(很多地方结合图形有利于理解分析)

首先,我们可以知道 C 的最后一个字母,要不是由 A的最后一个组成,要不就是B的最后一个组成,那么对于C的任意一位(这里说成)第 i + j 位要么就是由A的 i 位 或者 B 的 j 位组成,那么这个先给出 一个数组 dp[i][j] (它的行是由A的所有字母按顺序组成,列是B组成,比如题目的案例可以有以下图:

),它的值为 1 的时候表示 C 的 第 i + j 位 可以由A
的i 或者 B 的j 组成,为0 则表示不可以,那么我们对于整个的是否可以组成C我们可以用两个循环列举去组成的所有情况:for循环如下

	for(i=1;i<=a;i++)//a表示A的长度
	    for(j=1;j<=b;j++)//b表示B的长度

那么循环的过程就是求解dp这个二维方程组的过程,那么dp[i][j]的取值是怎么决定的呢?那么这里就涉及到 状态转移方程 dp[i][j] = ?

那么这里可以得到状态转移方程为:dp[i][j] = { (A[i] == c[i+j] && dp[i-1][j] == 1) || (B[j] == c[i+j] && dp[i][j-1]),那么为什么是这样转移的呢? 我们考虑dp[i][j] 的值得时候为 只是考虑如下两种情况(红色字标出的):

那么为什么要这样搭配出状态转移呢?

可以用下面的图理解:

由图可以知道,我们反过来就是得到dp[i][j]的思路

那么分析到这里,还有一个地方要注意,我们对于给出的那么dp[i][j]的二维数组前面的i=0的那一行和j=0的那一列空出来了,那就是要做边界处理的情况,我们要枚举每一种组成情况组成那么当然就有 c[i][j] i=0时 只有B的j组成c的情况。。。。

上马:

#include<stdio.h>
#include<string.h>

#define MAX 201

int dp[MAX][MAX];
char A[MAX],B[MAX],C[MAX*2];

int main()
{
	int T;
	int i,j;
	scanf("%d",&T);
	A[0]=B[0]=C[0]='0';
	for(int cas=1;cas<=T;cas++)
	{
		scanf("%s%s%s",A+1,B+1,C+1);//这里都从下标为1开始
		int a=strlen(A)-1,b=strlen(B)-1;

		for(i=1;i<=a;i++)//边界处理
			if(A[i]==C[i])	dp[i][0]=1;
			else            dp[i][0]=0;
			
		for(i=1;i<=b;i++)//边界处理
			if(B[i]==C[i])	dp[0][i]=1;
			else            dp[0][i]=0;

		for(i=1;i<=a;i++)
			for(j=1;j<=b;j++)
				dp[i][j]=((dp[i-1][j] && A[i]==C[i+j])||(dp[i][j-1] && B[j]==C[i+j]));

		printf("Data set %d: ",cas);
		if(dp[a][b])
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}

个人愚昧观点,欢迎指正与讨论

抱歉!评论已关闭.