CodeFestival2015本戦 G問題 スタンプラリー

むーーーこれは難しい。
Euler Tourという考え方で、行きがけ順の配列で木を表すというもの。
まぁそれをもとに今度は木を構成しなおすという話だが、解説スライドでは木と森という考え方を使っている。
実際にはまぁ仮想的な根を考えることで木の考え方だけで解ける。
今回は解説にあった方法を愚直に実装してみた。
この考え方天才的だ。最高。

constexpr ll mod = (ll)1e9+7;
constexpr int MAXN = 256;
int N;
int C[MAXN];
ll dp_tree[MAXN+1][MAXN+1];
ll dp_forest[MAXN+1][MAXN+1];

ll dfs_forest(int l, int r);

ll dfs_tree(int l, int r) //[l, r)でいくつ木が作れるか？
{
    if(r-l == 1) return 1; //要素がひとつになったら一つの木
    if(dp_tree[l][r] > 0) return dp_tree[l][r];
    ll ans = dfs_forest(l+1, r); //[l+1, r)の森にlを根としてつけたしたら木
    return dp_tree[l][r] = ans;
}

ll dfs_forest(int l, int r) //[l, r)でいくつ森が作れるか？
{
    if(r-l == 1) return 1; //要素がひとつになったら一つの森
    if(dp_forest[l][r] > 0) return dp_forest[l][r];
    ll ans = dfs_tree(l, r); //木は森
    for(int i=l+1; i<r; i++){ //[l, i)の木に[i, r)の森をつけたしたら森
        if(C[l] < C[i]){
            ans += dfs_tree(l, i)*dfs_forest(i, r);
            ans %= mod;
        }
    }
    return dp_forest[l][r] = ans;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) cin >> C[i], C[i]--;
    if(C[0] != 0){
        cout << 0 << endl;
        return 0;
    }

    cout << dfs_tree(0, N) << endl;
}