P3847的题解

典型到不能再典型的区间 dp 了。

观察四种操作，考虑到加一个数和删一个数的情况相同，所以无非就是：

1. 删一个数。

2. 改一个数。

设 \(dp[l][r]\) 为让区间 \(l\sim r\) 对称（变成回文串）的最少次数。

可以很快地得出状态转移方程：

情况 \(1\)：如果 \(a_l=a_r\)，则 \(dp[l][r]=dp[l+1][r-1]\)（该区间两端相同，令中间为回文串即可）。

情况 \(2\)：如果 \(a_l\not=a_r\)，我们则有三种方法变成回文串：

1. 改变 \(l\) 或 \(r\) 的值，此时 \(dp[l][r]=dp[l+1][r-1]+1\)。

2. 删除 \(l\)，此时 \(dp[l][r]=dp[l+1][r]+1\)。

3. 删除 \(r\)，此时 \(dp[l][r]=dp[l][r-1]+1\)。

情况 \(2\) 取三种方法的最小值即可。

枚举区间长度 \(len\) 与区间左端点 \(l\)，时间复杂度为 \(O(n^2)\)，可以通过此题。

#include<cstdio>
int min(int a,int b)
{
	return a<b?a:b;
}
int min(int a,int b,int c)
{
	return min(a,min(b,c));
}
int n;
int a[3010];
int dp[3010][3010];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int len=2;len<=n;len++)
		for(int l=1,r=l+len-1;r<=n;l++,r++)
		{
			if(a[l]==a[r]) dp[l][r]=dp[l+1][r-1];
			else dp[l][r]=min(dp[l+1][r-1],dp[l+1][r],dp[l][r-1])+1;
		}
	printf("%d",dp[1][n]);
	return 0;
}