< 题目链接 >
题目大意:
一个由小写字母组成的字符串, 给出字符的种类, 以及字符串的长度, 再给出添加每个字符和删除每个字符的代价, 问你要使这个字符串变成回文串的最小代价.
解题分析:
一道区间 DP 的好题. 因为本题字符串的长度最大为 2e3, 所以考虑 $O(n^2)$ 直接枚举区间的两个端点, 然后对枚举的区间进行状态转移, 大体上有三种转移情况:
$dp[l][r]$ 表示 $[l,r]$ 为回文串的最小代价
对于区间 $[l,r]$, 当 $str[l]==str[r]$ 时,$dp[l][r]=dp[l+1][r-1]$
对于 $dp[l+1][r]$ 情况, 即 $[l+1,r]$ 为回文串,$dp[l][r]=dp[l+1][r]+min($ 在 $r+1$ 添加 $str[l]$, 在 $l$ 删除 $str[l])$ 的代价
对于 $dp[l][r-1]$ 的情况, 即 $[l,r-1]$ 为回文串,$dp[l][r]=dp[l][r-1]+min($ 在 $l-1$ 添加 $str[r]$, 在 $r$ 删除 $str[r])$ 的代价
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int N = 2e3+5;
- int n,m,dp[N][N],add[26],del[26];
- char str[N];
- int main(){
- scanf("%d%d",&n,&m);
- scanf("%s",str+1);
- for(int i=1;i<=n;i++){
- char c;cin>>c;
- int pos=c-'a';
- scanf("%d%d",&add[pos],&del[pos]);
- }
- for(int i=m;i>=1;i--){
- dp[i][i]=0;
- for(int j=i+1;j<=m;j++){
- dp[i][j]=1e9;
- if(str[i]==str[j])dp[i][j]=dp[i+1][j-1];
- dp[i][j]=min(dp[i][j],dp[i+1][j]+min(add[str[i]-'a'],del[str[i]-'a']));
- dp[i][j]=min(dp[i][j],dp[i][j-1]+min(add[str[j]-'a'],del[str[j]-'a']));
- }
- }
- cout<<dp[1][m]<<endl;
- }
来源: http://www.bubuko.com/infodetail-3007941.html