洛谷2890 [USACO07OPEN]Cheapest Palindrome

题意

长度为 $N$ 的小写字母串，要求增加或删除字母使其变成回文串。每个字符的增加和删除有固定的花费，求花费的最小值。

$N\le 2000$ 。

题解

区间DP，用 $[i][j]$ 表示将 $[i,j]$ 变成回文串的最小花费。

如果 $S_i=S_j$ ，那么可以直接从 $f[i+1][j-1]$ 转移过来。

对于上一个状态 $[i+1,j]$ ，可以删掉 $S_i$ ，也可以在右边添加一个 $S_i$ 。 $[i,j-1]$ 同理。用 $v[x]$ 表示字符 $x$ 添加和删除的较小值，则方程式为：

$$f[i][j]=\min \begin{cases} f[i+1][j-1] \ (S_i=S_j) \\ f[i][j-1]+v[j] \\ f[i+1][j]+v[i] \end{cases}$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=2005,inf=0x3f3f3f3f;
char s[N],ch[5];
int n,m,f[N][N],v[N];

int dfs(int l,int r)
{
    if (l>=r) return 0;
    int &ans=f[l][r];
    if (ans<inf) return ans;
    ans=min(ans,dfs(l,r-1)+v[s[r]-'`']);
    ans=min(ans,dfs(l+1,r)+v[s[l]-'`']);
    if (s[l]==s[r]) ans=min(ans,dfs(l+1,r-1));
    return ans;
}

signed main()
{
    m=read(); n=read();
    scanf("%s",s+1);
    for (int i=1;i<=m;i++)
    {
        scanf("%s",ch); int cur=ch[0]-'`';
        v[cur]=read();
        v[cur]=min(v[cur],read());
    }
    memset(f,0x3f,sizeof(f));
    return !printf("%d",dfs(1,n));
}