首页 > ACM题库 > HDU-杭电 > hdu 2205 又见回文-动态规划-[解题报告]C++
2014
01-04

hdu 2205 又见回文-动态规划-[解题报告]C++

又见回文

问题描述 :

回文串就是对于一个字符串从前面向后读和从后面向前面读都是一样的,比如:mom。
对于这样一个具有魔力的回文串,爱好广泛的Eddy当然不会放过,他研究发现如果给他两个字符串s和t,然后把s和t交叉组成一个字符串,那么他可以马上知道在这个字符串的字串中最长的回文的子串的长度。现在举个例子:如果有s:AA,t:BB这样两个字符串,那么我们可以交叉得到6中方式:AABB BBAA ABAB BABA ABBA BAAB。其中第一第二个组合子串中的回文长度是2("AA"和"BB"),中间两种情况回文长度是3("ABA"和"BAB"),最后两种情况回文长度是4。所以该例的答案就是4.
现在Eddy想用这道题来考考你,不知道你准备好了吗?

输入:

本题有多组测试数据,每组输入为2行,第一行输入为s,第二行输入为t,特别地,某个输入串可能为空串,除了空字符串外其他均为大写字母(‘A’-'Z’)。
s和t的长度均小于50.

输出:

本题有多组测试数据,每组输入为2行,第一行输入为s,第二行输入为t,特别地,某个输入串可能为空串,除了空字符串外其他均为大写字母(‘A’-'Z’)。
s和t的长度均小于50.

样例输入:

AA
BB

JAVA
ONCEUPONATIMETHEREWASAYOUNGPROGRAMMERWHOLEARNED
TOPROGRAMJOINEDTOPCODERANDEVENTUALLYBECAMERED

样例输出:

4
3
9

OJ

本题是一道多元动规题,当初看到这道题只想可以用动规求解,只是不知道从哪里入手,后网上搜各种代码后得以释然,其实思想和实现好简单!

 假设str=a1a2a3…an,st = b1b2..bm

           取str中str(i,l1),st中st(j,l2),看这两个子串能否组成回文串,实际上若str[i] == str[i+l1-1] 可以得到子问题 str(i+1,l2-2) 与 st(j,l2)能否组成一个回文串,因为如果str(i+1,l2-2)与st(j,l2)能组成回文串的话,假设为S,那么我们可以把使str[i]+S+str[i+l1-1]x组成一个回文串。

           同理可以对st[j]==st[j+l2-1]讨论

           倘若上面的都不满足,还可以是str[i]==st[j+l2-1]或者是st[j]==str[i+l1-1] 假设能得到一个回文串S ,那么 str[i]+S+st[j+l2-1] 或者st[j]+S+str[i+l1-1]是回文串,这就转化为子问题的形式了。

          如此,转移方程就容易写了,只是注意点细节就行了!

#include<iostream>
#include<cstring>
using namespace std;
    char str[51],st[51];
    bool ar[51][51][51][51];
int main()
{
     int max,i,j,len1,len2,l1,l2;
	while (gets(str)&&gets(st))
	{
		len1=strlen(str);
		len2=strlen(st);
		memset(ar,0,sizeof(ar));
		max=0;
		for (i=0;i<=len1;i++)
			for (j=0;j<=len2;j++)
				ar[i][1][j][0]=ar[i][0][j][1]=ar[i][0][j][0]=true;
		for (l1=0;l1<=len1;l1++)
			for (l2=0;l2<=len2;l2++)
				for (i=0;i<=len1-l1;i++)
					for (j=0;j<=len2-l2;j++)
					{
						if (!ar[i][l1][j][l2])
							ar[i][l1][j][l2]=
								l1>1&&ar[i+1][l1-2][j][l2]&&str[i]==str[i+l1-1]||
								l2>1&&ar[i][l1][j+1][l2-2]&&st[j]==st[j+l2-1]||
								l1>0&&l2>0&&ar[i][l1-1][j+1][l2-1]&&str[i+l1-1]==st[j]||
								l1>0&&l2>0&&ar[i+1][l1-1][j][l2-1]&&str[i]==st[j+l2-1];
								if (ar[i][l1][j][l2]&&l1+l2>max) max=l1+l2;
					}
					cout<<max<<endl;
	}
	return 0;
}

解题转自:http://blog.csdn.net/gongqian12345/article/details/7730251


  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?