题解 [email protected]洛谷 【[USACO07OPEN]Cheapest Palindrome G】

小清新 dp 题喜加一。

题意:我们有一个字符串 ss,长度为 mm。我们可以在任意位置添加或删除一个字母,共有 nn 个字母可供选择,添加或删除不同字母所需花费不同,求使这个字符串为回文串的最少花费。


显然区间 dp,设计状态 dpi,jdp_{i,j} 表示使 sisjs_i\sim s_j 为回文串所需的最少花费。

下面考虑状态转移:

我们枚举区间长度 l[0,m)l\in\left[0,m\right),然后枚举左端点 ii,得到右端点 jj

对于一个回文字符串,在它的左侧加一个字符后要想保持回文性,有两种方法:在右侧添加一个同样的字符,或者将左侧字符删去。可以看出,对于一个字符而言,插入和删除的权值没有区别,可以只存最小值。

考虑这个字符串,我们可以看做它是由回文串在左侧添加一个字符得到的,也可以看做它是在右侧添加一个字符得到的。我们选择这两者的更小的那个即可:(mpmp 表示对于一个字符,插入和删除的权值中小的那个)

dpi,j=min(dpi+1,j+mpsi,dpi,j1+mpsj)dp_{i,j}=\min(dp_{i+1,j}+mp_{s_i},dp_{i,j-1}+mp_{s_j})

当然,有一种情况较为特殊:si=sjs_i=s_j,此时我们需要特判。如果 l1l\le 1,则该串本身回文, dpi,j=0dp_{i,j}=0。否则,dpi,j=min(dpi,j,dpi+1,j1)dp_{i,j}=\min(dp_{i,j},dp_{i+1,j-1})

于是,我们便得到了本题的三个方程。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int M = 2005;

int n, m;
string s;
map<char, int> mp;
int dp[M][M];

int main() {
	scanf("%d%d", &n, &m);
	cin>>s;
	memset(dp, 0x3f, sizeof(dp));
	for(int i=0;i<m;i++) {
		for(int j=0;j<=i;j++) dp[i][j] = 0;
	}
	for(int i=1;i<=n;i++) {
		char c = getchar();
		for(;c==' '||c=='\n';c=getchar());
		int a, b;
		scanf("%d%d", &a, &b);
		mp[c] = min(a, b);
	}
	for(int l=0;l<m;l++) {
		for(int i=0,j=l;j<m;i++,j++) {
			dp[i][j] = min(dp[i+1][j]+mp[s[i]], dp[i][j-1]+mp[s[j]]);
			if(s[i] == s[j]) dp[i][j] = min(dp[i][j], (l <= 1 ? 0 : dp[i+1][j-1]));
		}
	}
	printf("%d\n", dp[0][m-1]);
	return 0;
}