【51Nod】1092 - 回文字符串（LCS）

FishWang

发布于 2025-08-27 10:08:10

8800

代码可运行

运行总次数：0

代码可运行

点击打开题目

1092 回文字符串

基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级算法题

关注

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。

例如：abbc 添加2个字符可以变为 acbbca，也可以添加3个变为 abbcbba。方案1只需要添加2个字符，是所有方案中添加字符数量最少的。

Input

输入一个字符串Str，Str的长度 <= 1000。

Output

输出最少添加多少个字符可以使之变为回文字串。

Input示例

abbc

Output示例

添加或删除多少个字符使之构成回文串，其实和“删除多少字符构成回文串”是一样的（想一想，删除就是对应着添加嘛）

这类题要构造字符串a的翻转串，然后求一个LCS就行啦，然后总长度减去LCS就是结果。

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int dp[1011][1011];
void LCS(char *a,char *b,int l)
{
	for (int i = 0 ; i <= l ; i++)
		dp[l][0] = dp[0][l] = i;
	for (int i = 1 ; i <= l ; i++)
	{
		for (int j = 1 ; j <= l ; j++)
		{
			if (a[i-1] == b[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
		}
	}
}
int main()
{
	char a[1011];
	char b[1011];
	scanf ("%s",a);
	int l = strlen(a);
	for (int i = 0 ; i < l ; i++)
		b[i] = a[l - i - 1];
	b[l] = '\0';
	LCS(a,b,l);
	printf ("%d\n",l-dp[l][l]);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

int