Algoogle

Algorithm for Programming Contest

PKU 3280 Cheapest Palindrome

Category: PKU Tag: dp

Cheapest Palindrome

問題概要


文字列が与えられるのでその文字列に文字を挿入もしくは削除の操作をして回文にする際のコストの最小を求める.
各文字には挿入と削除のコストがそれぞれ決まっている.

解法


回文を生成するために文字列の両端だけをみるとき, 片方の文字を削除する場合というのはもう片方の外側に文字を付け加えるのと同じ.
例えばabcdeという文字列を両端から回文にしていくときにeを削除する場合abcdとeabcdeは同じ.
この文字列に文字を挿入または削除することで回文を作る場合は外側のeは無視して考えるのは明らか.
よってコストはどちらかの小さい方だけ使う.
あとはこの要領で始めは両端から見ていって, 毎回どちらかの端だけ操作して範囲を縮めるように再帰すればいい.

コード


(3280.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

typedef pair<int,int> pii;

const int inf = int(1e9);
int N, M, L;
string str;
int cst[26];

int memo[2048][2048];

int rec(int l, int r){
    if(memo[l][r] >= 0) return memo[l][r];
    if(r - l < 1) return memo[l][r] = 0;
    if(str[l] == str[r]) return memo[l][r] = rec(l+1,r-1);
    return memo[l][r] = min(rec(l ,r-1)+cst[str[r]-'a'], rec(l+1,r)+cst[str[l]-'a']);
}

int main(){
    cin >> N >> M;
    cin >> str;
    int L = str.size();
    for(int i = 0; i < N; i++){
        char c; int a, d;
        cin >> c >> a >> d;
        cst[c-'a'] = min(a, d);
    }
    memset(memo,-1,sizeof(memo));
    cout << rec(0, L-1) << endl;
    return 0;
}

Comments