P1435 [IOI2000] Palindrome String

Problem#

[IOI2000] Palindromic String#

A palindrome is a symmetric string. For any given string, by inserting several characters, it can be transformed into a palindrome. The task of this problem is to find the minimum number of characters that need to be inserted to turn the given string into a palindrome.

For example, inserting $2$ characters into $\verb!Ab3bd!$ can turn it into the palindrome $\verb!dAb3bAd!$ or $\verb!Adb3bdA!$, but inserting fewer than $2$ characters cannot make it a palindrome.

Note: This problem is case-sensitive.

Let the length of the string be $l$.

For all data, $0<l\le 1000$.

Solution#

Let f[i][j] represent the minimum number of steps to turn f[i][j] into a palindrome.

Then we consider three cases for the transition.

Code#

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