POJ 3280 Cheapest Palindrome（区间DP）

谁借莪１个温暖的怀抱￠ 2023-06-04 13:57 114阅读 0赞

嗯...

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

这道题首先要清楚：对于构成一个回文串，删去一个字符和加上一个字符是等效的，所以我们取花费较少的情况。

转移方程为：dp\[i\]\[j\] = dp\[i-1\]\[j-1\]（s\[i\]==s\[j\]）因为已经构成回文串，并且dp\[i-1\]\[j-1\]是最优的。

dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[i + 1\]\[j\] + use\[s\[i\] - 'a'\]) ——左边

*　*　　　　　dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[i\]\[j - 1\] + use\[s\[j\] - 'a'\]) ——右边

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<algorithm>
     5 
     6 using namespace std;
     7 
     8 char s[2005];
     9 int use[2005], dp[2005][2005];
    10 
    11 int main(){
    12     int n, m, x, y;
    13     char c;
    14     scanf("%d%d", &n, &m);
    15     scanf("%s", s + 1);
    16     for(int i = 1; i <= n; i++){
    17         cin >> c >> x >> y; 
    18         if(x < y) use[c - 'a'] = x;
    19         else use[c - 'a'] = y;
    20     }
    21     for(int l = 1; l <= m; l++){
    22         for(int i = 1; i <= m; i++){
    23             int j = i + l;
    24             if(j > m) break;
    25             dp[i][j] = 0x3f3f3f;
    26             if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
    27             else{
    28                 dp[i][j] = min(dp[i][j], dp[i + 1][j] + use[s[i] - 'a']);
    29                 dp[i][j] = min(dp[i][j], dp[i][j - 1] + use[s[j] - 'a']);
    30             }
    31         }
    32     }
    33     printf("%d\n", dp[1][m]);
    34     return 0;
    35 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11569515.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a23e2e1a614e453aa0c796e5671bab53.png