POJ 3280 - Cheapest Palindrome

http://poj.org/problem?id=3280

概要

\(N\) 種類の小文字のアルファベットのみからなる長さ \(M\) の文字列 \(s\) が与えられる。 各 \(N\) 種類の文字について追加・削除したときのコストがそれぞれ与えられる。 文字の追加・削除は好きな位置に行うことができ、位置によらずコストは一定である。 このとき、\(s\) を回文にするのに必要な最小のコストを答える。

制約

解法

区間 DP。

既にある区間が回文のとき、そこから回文の区間を広げるときに、 追加した文字を別の端に追加することと、今追加した文字を削除することは同じなので、 結局追加コストと削除コストのうち小さいほうのコストだけ考えればよい。

DP 表を

dp[i][j] = 区間 [i, j) を修正して回文にするための最小コスト

と定義し、

dp[i][i] = dp[i][i+1] = 0 (長さが 0, 1 の文字列は回文)
dp[i-1][j] := dp[i][j] + cost[i-1 番目の文字] (区間を左側にのばす)
dp[i][j+1] := dp[i][j] + cost[j 番目の文字] (区間を右側にのばす)
dp[i-1][j+1] := dp[i][j]  (i-1 番目の文字と j 番目の文字が等しいとき、コスト無しで区間を両側にのばす)

と更新していけばよい。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N, M;
 9   cin >> N >> M;
10   string s;
11   cin >> s;
12   int cost[26];
13   for (int i = 0; i < N; i++) {
14     string c;
15     int a, r;
16     cin >> c >> a >> r;
17     cost[c[0]-'a'] = min(a, r);
18   }
19 
20   static int dp[2000][2001];
21   static const int INF = 10000000;
22   for (int i = 0; i < M; i++) {
23     fill_n(dp[i], M+1, INF);
24     dp[i][i] = dp[i][i+1] = 0;
25   }
26   for (int len = 0; len < M; len++) {
27     for (int i = 0; i < M; i++) {
28       const int j = i+len;
29       if (i > 0) {
30         dp[i-1][j] = min(dp[i-1][j], dp[i][j] + cost[s[i-1]-'a']);
31       }
32       if (j < M) {
33         dp[i][j+1] = min(dp[i][j+1], dp[i][j] + cost[s[j]-'a']);
34       }
35       if (i > 0 && j < M && s[i-1] == s[j]) {
36         dp[i-1][j+1] = min(dp[i-1][j+1], dp[i][j]);
37       }
38     }
39   }
40   cout << dp[0][M] << endl;
41   return 0;
42 }
poj/3280.cc