poj 3280 字符串上的动态规划

谁践踏了优雅 2022-08-03 05:14 166阅读 0赞

添加或者删除一些字母，使这个字符串变成回文串。每个字母添加和删除的代价不一样。问最小代价。

看别人的思路，在字符串两端删除和添加字母是等价的，因此只需要保留删除和添加中最小的一个对字符串进行修改就行。

另外设置dp\[i\]\[j\]表示从i到j的变成回文串的最小代价，那么会有：

dp\[i\]\[j\]=dp\[i+1\]\[j-1\](a\[i\]==a\[j\])

dp\[i\]\[j\]=max(dp\[i+1\]\[j\]+w\[a\[i\]-'a'\],dp\[i\]\[j-1\]+w\[a\[j\]-'a'\])

//poj3280
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    char a[2222];
    int w[27];
    int dp[2002][2002];
    
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            getchar();
            gets(a);
            for(int i=0;i<n;i++)
            {
                char c=getchar();
                int t1=in();
                int t2=in();
                w[c-'a']=min(t1,t2);
            }
            mem(dp,0);
            for(int i=m-1;i>=0;i--)
            {
                for(int j=i+1;j<m;j++)
                {
                    if(a[i]==a[j])
                    {
                        dp[i][j]=dp[i+1][j-1];
                    }
                    else
                    {
                        dp[i][j]=min(dp[i+1][j]+w[a[i]-'a'],dp[i][j-1]+w[a[j]-'a']);
                    }
                }
            }
            printf("%d\n",dp[0][m-1]);
    
        }
        return 0;
    }