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;
}