P1435 [IOI2000] 回文字列

题目#

[IOI2000] 回文字串#

回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

比如 $\verb!Ab3bd!$ 插入 $2$ 个字符后可以变成回文词 $\verb!dAb3bAd!$ 或 $\verb!Adb3bdA!$，但是插入少于 $2$ 个的字符无法变成回文词。

注意：此问题区分大小写。

记字符串长度为 $l$。

对于全部数据，$0<l\le 1000$。

题解#

设 f [i][j] 表示把 f [i][j] 变成回文的最少步数

然后分三种情况转移

代码#

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;
char a[N];
int f[N][N];

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

int main()
{
	scanf("%s", a + 1);

	int n = strlen(a + 1);
	for(int i = 1;i <= n;i++)
	{
		f[i][i] = 0;
	}

	for(int i = 1;i < n;i++)
	{
		if(a[i] == a[i + 1])
		{
			f[i][i + 1] = 0;
		}
		else
		{
			f[i][i + 1] = 1;
		}
	}

	for(int L = 3;L <= n;L++)
	{
		for(int i = 1;i + L - 1 <= n;i++)
		{
			int j = i + L - 1;
			f[i][j] = min(f[i][j - 1] + 1, f[i + 1][j] + 1);

			if(a[i] == a[j])
				f[i][j] = min(f[i + 1][j - 1], f[i][j]);
		}
	}
	cout << f[1][n];
	return 0;
}