CODE FESTIVAL 2015 決勝 G - スタンプラリー

問題

code-festival-2015-final-open.contest.atcoder.jp

解法

絵がないと険しいので解説に丸投げします(ごめんなさい)。

CODE FESTIVAL 2015 解説 from AtCoder Inc.

www.slideshare.net

木 -> オイラーツアー -> 区間ごとに分けることが出来るじゃん, というのがベースですね。

得た知見

• 今までオイラーツアーってセグメント木でしか使ったことなかったけど確かに区間 DP でも使えるんですね
• dp_forest っていうのも賢いと思いました(小並感)
  • dp を 2 つタイプのやつ, 前も「次数が偶数(連結とは言っていない)」っていうのを数える dp と, 「オイラー路」を数える dp っていうのが SRM であったけど, それと同じようにより簡単な条件の dp を補助的に考えると上手く行くことがあるっぽい

const int MAXN = 300;
const ll MOD = 1e9+7;
int C[MAXN];
ll dpt[MAXN][MAXN], dpf[MAXN][MAXN];

void dfs(int l, int r) {
    if (dpt[l][r] >= 0) return;
    if (r-l == 1) {
        dpt[l][r] = dpf[l][r] = 1;
        return;
    }
    dpt[l][r] = dpf[l][r] = 0;
    for (int i = l+1; i < r; i++) {
        if (C[l] > C[i]) continue;
        dfs(l, i);
        dfs(i, r);
        dpf[l][r] += dpt[l][i] * dpf[i][r];
        dpf[l][r] %= MOD;
    }
    dfs(l+1, r);
    dpt[l][r] = dpf[l+1][r];
    (dpf[l][r] += dpt[l][r]) %= MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> C[i];
        C[i]--;
    }
    memset(dpt, -1, sizeof(dpt));
    memset(dpf, -1, sizeof(dpf));
    if (C[0] != 0) {
        cout << 0 << endl;
        return 0;
    }
    dfs(0, N);
    cout << dpt[0][N] << endl;
    return 0;
}