[poj]3280 Cheapest Palindrome http://poj.org/problem?id=3280
区间 dp
题意:
给你长度为 m 的字符串, 其中有 n 种字符, 每种字符都有两个值, 分别是插入这个字符的代价, 删除这个字符的代价, 让你求将原先给出的那串字符变成一个回文串的最小代价.
M<=2000
设 dp[i][j] 为区间 i~j 的回文串的最小代价
现在考虑怎样从别的状态转移到 区间 i~j
三种情况
首先 str[i]==str[j] 那么 dp[i][j] = dp[i+1][j-1]
其次 (i+1)~j 是一个回文串 dp[i][j] = dp[i+1][j] + (add[str[i]] / del[str[i]])
最后 i~(j-1) 是一个回文串 dp[i][j] = dp[i][j-1] + (add[str[j]] / del[str[j]])
代码:
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<iostream>
- #include<algorithm>
- #define APART puts("----------------------")
- #define debug 1
- #define FILETEST 1
- #define inf 2010
- #define ll long long
- #define ha 998244353
- #define INF 0x7fffffff
- #define INF_T 9223372036854775807
- #define DEBUG printf("%s %d\n",__FUNCTION__,__LINE__)
- namespace chino{
- inline void setting(){
- #if FILETEST
- freopen("_test.in", "r", stdin);
- freopen("_test.me.out", "w", stdout);
- #endif
- return;
- }
- inline int read(){
- char c = getchar(), up = c; int num = 0;
- for(; c <'0' || c> '9'; up = c, c = getchar());
- for(; c>= '0' && c <= '9'; num = (num <<3) + (num << 1) + (c ^ '0'), c = getchar());
- return up == '-' ? -num : num;
- }
- int n, m;
- char s[inf];
- int add[inf], del[inf];
- int dp[inf][inf];
- inline int main(){
- n = read(), m = read();
- scanf("%s", s + 1);
- for(int i = 1; i <= n; i++){
- char c = 0;
- std::cin>> c;
- add[c * 1] = read();
- del[c * 1] = read();
- }
- int len = strlen(s + 1);
- for(int i = 2; i <= len; i++){
- dp[i][i] = 0;
- for(int j = i - 1; j; j--){
- dp[j][i] = INF;
- if(s[i] == s[j])
- dp[j][i] = dp[j + 1][i - 1];
- dp[j][i] = std::min (dp[j][i] , dp[j + 1][i] + std::min (add[s[j] * 1], del[s[j] * 1]));
- dp[j][i] = std::min (dp[j][i] , dp[j][i - 1] + std::min (add[s[i] * 1], del[s[i] * 1]));
- }
- }
- printf("%d\n", dp[1][len]);
- return 0;
- }
- }//namespace chino
- int main(){return chino::main();}
[poj]3280 Cheapest Palindrome 题解
来源: http://www.bubuko.com/infodetail-3216294.html