首页 > 代码库 > HDU 1513

HDU 1513

题目出处:http://acm.hdu.edu.cn/showproblem.php?pid=1513

题目大意:

求如何在现有的字符串中添加有限个字符使其变成回文,且这有限个字符的个数尽量小。

本人错误思路:

刚开始的时候我把字符创分为两段,第二段逆序,和第一段求最大公共子序列,用第一段和第二段长度和减去公共子序列的二倍,我按给出的字符创的个数是奇数和偶数分成两种情况,但是发现很多测试数据都是错误的结果,让后又在里面分了好多情况,发现有找不完的错误数据,最终放弃,觉得思路整个就有错误。

赛后看了别人的思路:

将给出的字符串(S)逆序成(S`),求S与S`的公共子序列的长度(n)用字符创长度(len)减去公共序列长度(n)。

虽然比赛中脑子里也闪过这个想法,但是被自己的潜意识直接否定了。现在证明一下:

首先如果将S`直接追加在S后面组成的新的字符串一定是回文字符串,也就相当于在追加n个字符组成的新字符串形成回文串。但是这样已不是最小的,就算给出的串S是:ACBD,也不是在其后面添加死个字符而三个就可以了:ABCDCBA。那S与S`来看其实他们有很多公共的部分,直接拼接虽然是回文,但是如果可以把他们形成的部分凑成对称,这样的话就少添加一些元素,不难发现经过翻转的字符串S`和字符串S的对应位置是对称的,结合最长公共子序列不难发现:

*  z b c a d  e   *  b *  * * z  h    (1)

h z b *  *  *  e  d  *  a c b z  *    (2)
所以(1)中或者(2)中的星号的个数就为要添加最小元素个数。


由于本题数据规模比较大,所以作为二维区间的的DP超过了题目给的内存.但是熟悉最长公共子序列的同学,会发现,由于每次规划最多用到那个二维区间的两行,所以可以循环利用这两行,提高内存利用率。下面是我的代码:

#include<iostream>
#include<cstdio>
using namespace std;

char str1[5010],str2[5010];
short dp[2][5010];

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		getchar();
		int i,j;

		int len;
		for(i=0;i<n;i++)
			scanf("%c",&str1[i]);
		for(i=0;i<n;i++)//逆序。
			str2[n-1-i]=str1[i];

		for(i=0;i<=n;i++)//初始化。第一行全部为零,第二行的第一个数为0;
			dp[0][i] = 0;

			dp[1][0] = 0;

		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				if(str1[i]==str2[j])
				{
					dp[1][j+1] = dp[0][j] + 1;
				}
				else
				{
					if(dp[0][j+1]>dp[1][j])
						dp[1][j+1] = dp[0][j+1];
					else
						dp[1][j+1] = dp[1][j];
				}
			}
			for(j=0;j<=n;j++)//把本行按照算法打出的一行变为第一行,
<span style="white-space:pre">					</span>//这样就可以在第二行算出下一行。
				dp[0][j] = dp[1][j];

				dp[1][0] = 0;

		}
		printf("%d\n",n-dp[1][n]);
	}
	return 0;
}

HDU 1513