POJ 3280 Cheapest Palindrome(区间DP)
嗯…
题目链接: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代码:
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代码
转载于//www.cnblogs.com/New-ljx/p/11569515.html
还没有评论,来说两句吧...