NYOJ 1023 还是回文(DP,花最少费用形成回文串)

 /*

    题意：给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。

    那么，将字符串变成回文串的最小花费是多少呢？ 

    思路：如果一个字符串增加一个字符 x可以形成一个回文串，那么从这个字符串中删除这个字符 x

          同样也能形成回文串！

          所以我们只记录删除，和增加这个字符 x 的最小的费用就好了！->转变成添加多少个字符形成回文串费用最少！ 

          str[i]!=str[k]

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

          str[i]==str[k]

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

 */

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #define N 2005

 using namespace std;

 int dp[N][N];

 int cost[]; 

 char str[N]; 

 int main(){

     int m, n;

     while(scanf("%d%d", &m, &n)!=EOF){

         scanf("%s", str+);

         memset(cost, , sizeof(cost));

         while(m--){

            char ch;

            int a, b;

            getchar();

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

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

         }

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

            dp[i][]=;

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

            for(int i=; i+j-<=n; ++i){

                int k=i+j-;

                if(str[i]!=str[k])

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

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

            }   

         printf("%d\n", dp[][n]);

     }

     return ;

 } 

NYOJ 1023 还是回文(DP,花最少费用形成回文串)的相关教程结束。