POJ 3280 Cheapest Palindrome(区间DP)

谁借莪1个温暖的怀抱¢ 2023-06-04 13:57 185阅读 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. 1 #include<cstdio>
  2. 2 #include<iostream>
  3. 3 #include<cstring>
  4. 4 #include<algorithm>
  5. 5
  6. 6 using namespace std;
  7. 7
  8. 8 char s[2005];
  9. 9 int use[2005], dp[2005][2005];
  10. 10
  11. 11 int main(){
  12. 12 int n, m, x, y;
  13. 13 char c;
  14. 14 scanf("%d%d", &n, &m);
  15. 15 scanf("%s", s + 1);
  16. 16 for(int i = 1; i <= n; i++){
  17. 17 cin >> c >> x >> y;
  18. 18 if(x < y) use[c - 'a'] = x;
  19. 19 else use[c - 'a'] = y;
  20. 20 }
  21. 21 for(int l = 1; l <= m; l++){
  22. 22 for(int i = 1; i <= m; i++){
  23. 23 int j = i + l;
  24. 24 if(j > m) break;
  25. 25 dp[i][j] = 0x3f3f3f;
  26. 26 if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
  27. 27 else{
  28. 28 dp[i][j] = min(dp[i][j], dp[i + 1][j] + use[s[i] - 'a']);
  29. 29 dp[i][j] = min(dp[i][j], dp[i][j - 1] + use[s[j] - 'a']);
  30. 30 }
  31. 31 }
  32. 32 }
  33. 33 printf("%d\n", dp[1][m]);
  34. 34 return 0;
  35. 35 }

AC代码

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

发表评论

表情:
评论列表 (有 0 条评论,185人围观)

还没有评论,来说两句吧...

相关阅读

    相关 poj 2253(区间DP

    [原题][Link 1] 思路:求所有路径中最大跳跃距离的最小值, 很诡异的是输出答案如果用G++,.3lf%格式会出错,c++可以过 include<cstdio

    相关 POJ1179 Polygon(区间dp

    题意:多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“\”。所有边依次用整数从1到n编号,游戏第1