poj 3280 Cheapest Palindrome (DP)

poj 3280 Cheapest Palindrome (DP)

題意：有一個由n個小寫字母組成的，長度為m的字符串，可以對其通過增加字符或者刪除字符來使其變成回文。而增加或者刪除字符都有一個花費，求解使該字符串變成回文的最小花費。

思路：DP。dp[i][j]表示串str[i~j]變成回文的最小代價，故狀態轉移方程為：

當str[i] == str[j]時 dp[i][j] = dp[i+1][j-1];
當str[i] != str[j]時 dp[i][j] = min( dp[i+1][j]+add[str[i]-'a'], dp[i][j-1]+add[str[j]-'a'],

dp[i+1][j]+del[str[i]-'a'], dp[i][j-1]+del[str[j]-'a']);

其實dp很難逃出3種思路：

1、一維線性dp：每次考慮i時，選擇最優子問題要麼在i-1，要麼在1...i-1裡；

2、二維線性dp：考慮(i,j)子問題時，選擇最優子問題要麼在(i+1,j)、(i,j-1)，要麼在i<= k <=j，在k裡；

3、樹形dp：考慮i節點最優時，選擇子節點最優，一般融合了01背包dp的雙重dp。

上面3中模式也是我在做題後才發現的。

這個dp題其實就可以仿照第2中思路。

假設一個字符串Xx....yY；對於求這個字符串怎麼求呢？

分4中情況討論：

1、去掉X，取x....yY回文；

2、去掉Y，取Xx....y回文；

3、在左邊加上X,取Xx....yYX回文；

4、在右邊加上Y,取YXx....y回文。

至於去掉X、Y肯定沒有第1、2中情況合算；加上X、Y肯定沒有第3、4中情況合算。

因此令dp[i][j]為i...j要變成回文字符串的最小代價。

方程：

dp[i][j] = min{ dp[i+1][j] + {去掉X的代價}，dp[i+1][j] + {加上X的代價}，dp[i][j-1]+ {去掉Y的代價}，dp[i][j-1] +{加上Y的代價}}；

其實分析發現，對於X而言，只要去 去掉 和加上 X 最小代價就行（因為前面dp串一樣）,Y同理。

因此最後得出：

dp[i][j] = min{ dp[i+1][j] +min{ {去掉X的代價}, {加上X的代價}}，dp[i][j-1]+min{ {去掉Y的代價}, {加上Y的代價}}}；

dp時候還有些注意事項：

比如當X和Y字符一樣時，則在dp時必須先為x...y的最小代價。

源代碼：(14056K, 79MS)
#include
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int MAX = 2005;
 
int dp[MAX][MAX];
int add[30], del[30];
 
int main(){
    int n, m, i, j, len;
    char c, str[MAX];
    cin >> n >> m >> str;
    for(i = 0; i < n; i ++){
        cin >> c;
        cin >> add[c-'a'] >> del[c-'a'];
    }
    for(len = 1; len < m; len ++)
        for(i = 0; i + len < m; i ++){
            j = i + len;
            if(str[i] == str[j]){
                dp[i][j] = dp[i+1][j-1];
            }else{
                dp[i][j] = min(
                    min(dp[i+1][j]+add[str[i]-'a'], dp[i][j-1]+add[str[j]-'a']),
                    min(dp[i+1][j]+del[str[i]-'a'], dp[i][j-1]+del[str[j]-'a']));
            }
        }
    cout << dp[0][m-1] << endl;
    return 0;
}