Poj 3280: Cheapest Palindrome

poj3280.md

Poj 3280: Cheapest Palindrome

題目

分析

標準二維 dp 的題型。

###定義

Let dp[i][j] = 使 S[i:j+1) 變成迴文的最小成本

答案為 dp[0][M-1]

###轉移方程式：

考慮字串 Ax...yB（符號僅表示相對位置），使這個字串變迴文的最小成本，有下列五種可能。

1. 若 A = B，則成本為使 x...y 變迴文的成本

2. 刪掉 A 的成本 + 使 x...yB 變迴文的成本

3. 刪掉 B 的成本 + 使 Ax...y 變迴文的成本

4. 加入 A 的成本 + 使 x...yB 變迴文的成本（字串變為 Ax...yBA，這時只要使 x...yB 變為迴文，整個字串就是迴文）

5. 加入 B 的成本 + 使 Ax...y 變迴文的成本（字串變為 BAx...yB，這時只要使 Ax...y 變為迴文，整個字串就是迴文）

答案就是在上面五種可能裡取最小值，所以

dp[i][j] = min(dp[i+1][j] + del[S[i]],
			   dp[i][j-1] + del[S[j]],
			   dp[i+1][j] + add[S[i]],
			   dp[i][j-1] + add[S[j]])
if S[i] == S[j]:
	dp[i][j] = min(dp[i][j], dp[i+1][j-1])

※ 有人可能會有疑惑，為什麼 刪除 A + 加上 B + dp[i+1][y-1] 這種情況不用考慮？這是因為這種情況會在求解 dp[i][j-1] 時被可慮到。

###順序

採用 Top-down DP 就可以不用費心的找順序。

只是在遞迴的過程中可能出現須求解 dp[i][j] i >= j 的情況，此時 dp[i][j] = 0 。

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>

using namespace std;

int N, M;
string S;
int add[26];
int del[26];
int dp[2000][2000];

int solve(int i, int j) {
    if (dp[i][j] != -1)
        return dp[i][j];

    if (i >= j)
        return (dp[i][j] = 0);

    dp[i][j] = min(solve(i+1, j) + min(del[S[i] - 'a'], add[S[i] - 'a']),
                   solve(i, j-1) + min(del[S[j] - 'a'], add[S[j] - 'a']));
    if (S[i] == S[j])
        dp[i][j] = min(dp[i][j], solve(i+1, j-1));

    return dp[i][j];
}

int main() {
    cin >> N >> M;
    cin >> S;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        cin >> add[c - 'a'] >> del[c - 'a'];
    }

    memset(dp, -1, sizeof(dp));
    cout << solve(0, M-1) << "\n";

    return 0;
}