题目：

POJ3280

洛谷2980

分析：

首先，考虑只可以加字的情况

设$s[i]$表示第$i$个字符，$add[i]$表示加上一个字母$i$的花费，$dp[i][j]$表示把区间$i$~$j$变成回文串的花费，那么

1.如果$s[i]=s[j]$，那么只需要把$(i+1)$~$(j-1)$变成回文串就可以了，

即

\[dp[i][j]=dp[i+1][j-1]
\]

2.如果$s[i] \neq s[j]$，那么可以先把$i$_{$(j-1)$变成回文串，然后在前面加一个$s[j]$，和$i$}$j$串尾的$s[j]$对应上，

即

\[dp[i][j]=dp[i][j-1]+add[s[j]]
\]

同理，也可以先把$(i+1)$_{$j$变成回文串，然后在后面加一个$s[i]$，和$i$}$j$串首的$s[i]$对应上，

即

\[dp[i][j]=dp[i+1][j]+add[s[i]]
\]

在这两种方法中取花费较小的一个。

边界条件：当$i=j$，只有一个字符的字符串显然是回文串

然后考虑还可以减字的情况

设$del[i]$表示减去一个字母i的花费，其余同上。

显然，$s[i]=s[j]$的情况是不受影响的。

我们来讨论$s[i] \neq s[j]$的情况：

我们也可以先把$i$_{$(j-1)$变成回文串，然后删掉$i$}$j$串尾的$s[j]$，这样它就变成回文串了

即

\[dp[i][j]=dp[i][j-1]+del[s[j]]
\]

发现什么了？这只是把上面的第二个状态转移方程中$add[s[j]]$变成了$del[s[j]]$!

同理，也有

\[dp[i][j]=dp[i+1][j]+del[s[i]]
\]

总结一下，当$s[i] \neq s[j]$时，一共有如下四种转移，取最小值即可：

\[dp[i][j]=dp[i][j-1]+add[s[j]]
\]

\[dp[i][j]=dp[i+1][j]+add[s[i]]
\]

\[dp[i][j]=dp[i][j-1]+del[s[j]]
\]

\[dp[i][j]=dp[i+1][j]+del[s[i]]
\]

其实到这里已经可以写这道题了，但是可以发现一个有趣的事情

如果设$c[i]=min(add[i],del[i])$，那么……

第一个和第三个方程合作一下得到：

\[dp[i][j]=dp[i+1][j]+c[s[i]]
\]

第二个和第四个方程合作一下得到：

\[dp[i][j]=dp[i][j-1]+c[s[j]]
\]

所以这题的可以加减字符就是个幌子，取每个字符加字和减字的较小值作为该字符的花费就可以啊2333

代码：

(注意一下字符的读法，一定要防止读进来' '或者'\n'之类奇怪的东西）

#include<cstdio>

#include<algorithm>

using namespace std;

int dp[2010][2010],n,m,cost[26];

const int INF=0x3f3f3f3f;

char s[2010];

int main(void)

{

	scanf("%d%d%s",&n,&m,s);

	for(int i=0;i<n;i++)

	{

		char a;

		int b,c;

		do{a=getchar();}while(!('a'<=a&&a<='z'));

		scanf("%d%d",&b,&c);

		cost[a-'a']=min(b,c);

	}

	for(int len=2;len<=m;len++)

		for(int i=0;i<=m-len;i++)

		{

			int j=i+len-1;

			dp[i][j]=INF;

			if(s[i]==s[j])

				dp[i][j]=dp[i+1][j-1];

			else

				dp[i][j]=min(dp[i+1][j]+cost[s[i]-'a'],dp[i][j-1]+cost[s[j]-'a']);

		}

	printf("%d",dp[0][m-1]);

	return 0;

}

秒客网

【POJ3280/洛谷2890】[Usaco2007 Open Gold]Cheapest Palindrome（动态规划）

题目：

POJ3280

洛谷2980

分析：

代码：