mayoko’s diary

プロコンとかいろいろ。

IndeedなうB:C問題:Palindrome Concatenation

回文判定はなんか浮いたことしちゃったのかも。

問題:C: Palindrome Concatenation - Indeedなう(オープンコンテストB) | AtCoder

解法:dp[n]=(n文字目までの最小コスト)とすると,dp[n]=min(dp[k]+(n-k文字の回文のコスト))という感じになる。これを高速で実行するためにまず回文判定をO(N^2)でやることを考える。
本番考えたやり方は以下の通り。まず回文の文字数が奇数の時はわかりやすくて,
a->bab->cbabc
というように,真ん中からその両端が同じなら更に次の文字を調べて回文をどんどん広げていく。ただ、回文が偶数の時は元の回文(上の例でいうと"a")がないのでやりづらい。そこで,元の文字列の間に"?"を挿入して上と同じように考えると,例えば
?->a?a->?a?a?->b?a?a?b
というのは,元の文字列ではbaabという回文を判定をしたことになる。
以下ソースコード

const int MAXN = 5100;
int C[MAXN];
vector<int> back[MAXN]; // 回分になるポイント
int dp[MAXN];

int main(void) {
    int N;
    cin >> N;
    string s;
    cin >> s;
    for (int i = 0; i < N; i++) cin >> C[i];
    // 回文になっているところを調べる
    string t;
    for (int i = 0; i < N; i++) {
        t += s.substr(i, 1);
        t += "?";
    }
    int nn = t.size();
    for (int i = 0; i < nn; i++) {
        int cur = 1;
        while (1) {
            if (i-cur < 0 || i+cur >= nn) break;
            if (t[i-cur] != t[i+cur]) break;
            int tmp = i+cur;
            if ((tmp&1) == 0) { // ?のところじゃない時
                back[tmp/2].push_back(tmp/2-cur);
            }
            cur++;
        }
    }
    // dp
    for (int i = 1; i <= N; i++) {
        dp[i] = dp[i-1] + C[0];
        for (int j = 0; j < (int)back[i-1].size(); j++) {
            dp[i] = min(dp[i], dp[back[i-1][j]] + C[i-1-back[i-1][j]]);
        }
    }
    cout << dp[N] << endl;
    return 0;
}