SRM 499 div1 med:WhiteSpaceEditing(その2)

前の記事(SRM 499 div1 med:WhiteSpaceEditing - mayoko’s diary)では貪欲法で解いてしまいましたがdpに慣れたほうが明らかに成績が安定するのでそっちも練習してみました。

解法:topcoderの解説(Login - TopCoder Wiki)を参考にしました。
区間DPというDPを使います。把握しておかなければならない事実は先ほどと同じで,30,20,10とかを作りたい時10から作って逆戻りする見たいのはわかってないとダメです。
で,多分プロの人は問題を見た時点でなんとか区間DPの形に持ち込もうとしています。基本的なアイデアとしては,例えば
2,2,2,6,6,6,6,2,2,2
という文章を作りたい時,実際の操作としては
2,2,2,2,2,2,2
と2を7個作ってから
2,2,2,6,2,2,2
と2の一つを6に変えて
2,2,2,6,6,6,6,2,2,2
というようにしますが,区間DPの形にするためにちょっと問題を変えて,最初から9行分文章が存在して(改行は行数nが決まれば強制的にn-1回しなければならないので後でn-1足して答えにする),

2,2,2,2,2,2,2,2,2,2
という文章をまず「2をひとつ作って,改行を9回する」という作業をして作ってから
2,2,2,6,2,2,2,2,2,2 -> 2,2,2,6,6,6,6,2,2,2
というように6を増やしていくというように考えます。すると,改行は操作の回数に含めないとすると操作の回数は
・2を作るのに2回
・2から6を作るのにスペースを4回打つので4回
の合計6回になります。そのあと改行の操作の9回分を足して15回です。

このような考え方をすると区間DPに持ち込みやすいです。どのように区間DPにするかというと,
・区間[l, r)全体に何個のスペースを入れるか,という数をlines[h]とする
・r-l == 1というベースとなるケースでは,必要な操作回数はabs(lines[i]-lines[h])回(DELETEするかINSERTするか)
・それ以外の場合は区間を[l,m)と[m,r)に分けてそれぞれについて必要な回数を計算する

という感じです。下のソースコードではdfs(l, r, h, mode)というのがそれをやっています。modeというのが上の説明に出てきてませんが,これは計算量削減のためです。具体的には,
普通にやるとdfsのところで中間になるmとどのスペース量を選択するかのiで二重ループにしないといけないため,状態量O(n^3)*各状態量の計算O(n^2) = 全体の計算量O(n^5)となりますがこれは結構危ないです(定数倍削減でO(10^8)くらいだから多分間に合うけど)。
なのでそのmとiの選択を二段階に分けてO(n^4)にしました。
以下ソースコード

const int INF = (1<<30);
int dp[55][55][55][2];
vector<int> len;
int n;

int dfs(int l, int r, int h, int mode) {
    if (r-l == 1) {
        return abs(len[h]-len[l]);
    }
    int& ret = dp[l][r][h][mode];
    if (ret >= 0) return ret;

    ret = INF;
    if (mode == 0) {
        for (int i = 0; i < n; i++) {
            ret = min(ret, abs(len[h]-len[i]) + dfs(l, r, i, 1));
        }
    } else {
        for (int m = l+1; m < r; m++) {
            ret = min(ret, dfs(l, m, h, 0) + dfs(m, r, h, 0));
        }
    }
    return ret;
}

class WhiteSpaceEditing {
public:
    int getMinimum(vector <int> lines) {
        n = lines.size();
        len = lines;
        len.push_back(0);
        memset(dp, -1, sizeof(dp));
        return dfs(0, n, n, 0) + (n-1);
    }
};