poj（3280）Cheapest Palindrome（区间dp）

阳光穿透心脏的1/2处 2022-08-26 15:36 93阅读 0赞

题目链接：[http://poj.org/problem?id=3280][http_poj.org_problem_id_3280]

题意：给出一个由m中字母组成的长度为n的串，给出m种字母添加和删除花费的代价，求让给出的串变成回文串的代价。

分析：我们知道求添加最少的字母让其回文是经典dp问题，转化成LCS求解。这个是一个很明显的区间dp

我们定义dp \[ i \] \[ j \] 为区间 i 到 j 变成回文的最小代价。

那么对于dp【i】【j】有三种情况

首先：对于一个串如果s【i】==s【j】，那么dp【i】【j】=dp【i+1】【j-1】

其次：如果dp【i+1】【j】是回文串，那么dp【i】【j】=dp【i+1】【j】+min（add【i】，del【i】）；

最后，如果dp【i】【j-1】是回文串，那么dp【i】【j】=dp【i】【j-1】 + min（add【j】，del【j】）；

代码：

#include <cstdio>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 200;
    const int M = 2500;
    int add[N];
    int dp[M][M];
    
    int main()
    {
        int n,m;
        string s;
        while(~scanf("%d%d",&n,&m))
        {
            cin>>s;
            char c;int x,y;
            for(int i=0;i<n;i++)
            {
                cin>>c>>x>>y;
                add[c]=min(x,y);
            }
            memset(dp,0,sizeof(dp));
            for(int k=1;k<s.size();k++)
            {
                for(int i=0,j=k;j<s.size();i++,j++)
                {
                    dp[i][j]=0x3f3f3f3f;
                    if(s[i]==s[j])
                        dp[i][j]=dp[i+1][j-1];
                    else
                    {
                        dp[i][j]=min(dp[i+1][j] + add[s[i]],dp[i][j]);
                        dp[i][j]=min(dp[i][j-1] + add[s[j]],dp[i][j]);
                    }
                }
            }
            printf("%d\n",dp[0][s.size()-1]);
        }
        return 0;
    }

[http_poj.org_problem_id_3280]: http://poj.org/problem?id=3280