poj 3280 Cheapest Palindrome(区间dp) - dblank

poj 3280 Cheapest Palindrome(区间dp)

题目链接:http://poj.org/problem?id=3280

题意:给你一个字符串,然后给你一个字符表,里面有删除和添加这个字符的代价,问你把他最后变成回文串的最小代价。

思路:我们可以dp[i][j]表示从第i个字符到第j个字符变成回文串的最小代价,然后对应dp[i+1][j]和dp[i][j-1]我们可以选择删除和添加对应字符的最小代价,如果s[i] == s[j] 的话,就直接从dp[i+1][j-1]1转移。

注意:循环的遍历方式一定要保证转移的状态是已经变成回文串的代价,还有如果j<=i,dp[i][j]是等于0的,其他要初始化为大值。

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
#include<cmath>  
using namespace std;  
const double eps = 1e-10;  
const int inf = 0x7fffffff, N = 3e5 + 10;  
typedef long long ll;  
using namespace std;  
int add[30], del[30], dp[2020][2020], u, v;  
char s[2010], x;  
int main()  
{  
    int n, m;  
    while(cin>>n>>m)  
    {  
        scanf("%s", s+1);  
        memset(del, -1, sizeof(del));  
        memset(add, -1, sizeof(add));  
        for(int i = 0; i<n; i++)  
        {  
            scanf(" %c%d%d", &x, &u, &v);  
            add[x-'a'] = u;  
            del[x-'a'] = v;  
        }  
        memset(dp, 0x3f, sizeof(dp));  
        for(int i = 1; i<=m; i++)  
            for(int j = 1; j<=i; j++)  
                dp[i][j] = 0;  
        for(int i = m; i>=1; i--)  
            for(int j = i+1; j<=m; j++)  
            {  
                dp[i][j] = min(dp[i+1][j] + min(del[s[i]-'a'], add[s[i]-'a']), dp[i][j-1] + min(del[s[j]-'a'], add[s[j]-'a']));  
                if(s[i] == s[j])  
                    dp[i][j] = min(dp[i+1][j-1], dp[i][j]);  
            }  
        cout<<dp[1][m]<<endl;  
    }  
    return 0;  
}  

 

相关文章

发表新评论