B - Reversi

B - Reversi

解法

まず、操作に選ばれた区間は交わらないと考えていい。

ここで、選ばれなかった石を長さ一の区間とみなすと、この問題はN個の石をいくつかの区間に分割する問題となる。

区間が交わらないことから、dp[i] := iまでを分割する方法としてまとめられ

dp[n]が答えとなる。

************遷移について**************

0 1 2 3 4 5 6 7 8   : index)

""1 4 1 2 1 2 2 1   : 数列

例えば、5番目の'1'について。

3と対応付けた場合の5までの分割方法はdp[2]となる。

同様にして、dp[5] = dp[0] + dp[2] + dp[4](対応付けない場合) となる

また、8番目の'1'の場合　dp[8] = dp[0] + dp[2] + dp[4] + dp[7]

　　　　　　　　　　　　　　= dp[5] + dp[7]

となる事から、a[i]の値毎に足す値を累積して持てば、O(1)で解ける事が分かる

また、22222 のように連続した区間がある場合、塗り分け方は1つだが、複数の分割が数え上げられてしまう。

12223 -> 123のように連続するものを消すと上手くいく。

Submission #4610087 - AtCoder Grand Contest 031

void solve() {
    cin >> n;
    na(a, n);
    unique(a);
    n = a.size();
    push_front(a, 0);
    setMod();
    vm ad(k5 * 2);
    vm dp(k5 * 2);
    dp[0] = 1;
    rep(i, 1, n + 1) {
        int v = a[i];
        dp[i] += dp[i - 1] + ad[v];
        ad[v] += dp[i - 1];
    }
    cout << dp[n] << endl;
}