BZOJ1710: [Usaco2007 Open]Cheappal 廉价回文

len<=2000的字符串上，给出删掉和添加每种字符的花费，求把字符串变成回文串的最小花费。

首先每个字符添加和删除是一样的，因此花费在添加和删掉每个字符的花费中取小的。

如果每个字符的花费都是1，就是找最长回文串再用len减掉即可。（manacher！）

加了花费同理，就是找“最大权回文串”再用每个字符的花费总和减掉即可。

字符串上的区间DP，f[i][j]--区间[i,j]的最大权回文串的权

若s[i]=s[j]:f[i][j]=f[i+1][j-1]+2*v[s[i]]，v[s[i]]表示字符s[i]的花费

若s[i]!=s[j]:f[i][j]=max(f[i+1][j],f[i][j+1])

注意dp顺序，从小区间到大区间。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 //#include<iostream>

 using namespace std;

 int n,len;

 #define maxs 2017

 int f[maxs][maxs],v[],sum;

 char s[maxs];

 char c[];

 int x,y;

 int main()

 {

     scanf("%d%d",&n,&len);

     scanf("%s",s);

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

     {

         scanf("%s",c);

         scanf("%d%d",&x,&y);

         v[c[]-'a']=min(x,y);

     }

     memset(f,,sizeof(f));

     sum=;

     for (int i=;i<len;i++)

     {

         sum+=v[s[i]-'a'];

         f[i][i]=v[s[i]-'a'];

     }

     for (int j=;j<len;j++)

         for (int i=;i<len-j+;i++)

             f[i][i+j]=s[i]==s[i+j]?f[i+][i+j-]+*v[s[i]-'a']:max(f[i+][i+j],f[i][i+j-]);

     printf("%d\n",sum-f[][len-]);

     return ;

 }

巴特西

BZOJ1710: [Usaco2007 Open]Cheappal 廉价回文

最新文章

热门文章