CVBB ACM Team

POJ 3280

每个字母有给定的删除\增添代价，问使得字符串变为回文串的最小花费。

题解：这个题是这样，当看到区间dp的那一刻就会了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,m,ad[26],de[26],f[2005][2005];
char s[2005];
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		scanf("%s",s);
		for(int i=1;i<=n;i++)
		{
			char c;
			scanf(" %c",&c);
			scanf("%d%d",&ad[c-'a'],&de[c-'a']);
		}
		for(int k=1;k<=m;k++)
		{
			for(int i=0;i<m;i++)
			{
				int j=i+k-1;
				if(k==1)f[i][j]=0;
				else
				{
					f[i][j]=min(f[i+1][j]+de[s[i]-'a'],f[i][j-1]+de[s[j]-'a']);
					f[i][j]=min(f[i][j],f[i+1][j]+ad[s[i]-'a']);
					f[i][j]=min(f[i][j],f[i][j-1]+ad[s[j]-'a']);
					if(s[i]==s[j])f[i][j]=min(f[i][j],f[i+1][j-1]);
				}
			}
		}
		printf("%d\n",f[0][m-1]);
	}
	return 0;
}