本番時間切れ。
http://codeforces.com/contest/509/problem/F
問題
N頂点の木をなすグラフがあるとする。
1番の頂点から始め、隣接する若い番号の順にDFSするアルゴリズムにより、全頂点を探索することを考える。
前記アルゴリズムによる初訪問の頂点番号順B[i]が与えられる。
そのような訪問順になる木は何通りあるか答えよ。
解法
以下の2値を使いDPしていく。
変数名はEditorial準拠。
- D(L,R): B[L]から初めてB[L]~B[R]をDFSで訪問できるような木の組み合わせ数。
- E(L,R): B[L..R]は番号順にいくつかのサブツリーに分けられ、各サブツリーB[x..y]はB[x]からDFSで訪問できる。また各サブツリーの根の番号は昇順である。というようなサブツリー群の組み合わせ。
D(L,R)及びE(L,R)は以下のように求められる。
- E(L,R)はLを根としてB[(L+1)..R]をサブツリーに持つと考えると、E(L,R)=D(L+1,R)
- D(L,R)は以下の和:
- 全体が1つのサブツリーになる場合、すなわちE(L,R)。
- B[L..(x-1)]の単一サブツリーと、B[x..R]のいくつかのサブツリーに分割できる場合、すなわち
B[L]<B[x]となるL<x≦Rに対し、D(L,x-1)*E(x,R)の和。
D(i,i)やE(i,i)は1。
ここからD(i,i+w)、E(i,i+w)をだんだんwを広げながら求めて、最終的にD(1,N)が答え。
int N,B[600]; ll mo=1000000007; ll pat; ll sp[502][502]; ll sub[502][502]; void solve() { int i,j,k,l,r,x,y,w; string s; cin>>N; pat=1; FOR(i,N) cin>>B[i], sp[i][i]=sub[i][i]=1; for(w=1;w<N;w++) { for(l=0;(r=l+w)<N;l++) { sp[l][r]=sub[l][r]=sp[l+1][r]; for(x=l+1;x<=r;x++) if(B[l]<B[x]) sp[l][r]+=sub[l][x-1]*sp[x][r]%mo; sp[l][r] %= mo; } } cout<<sub[0][N-1]<<endl; }
まとめ
終わってみるとコードはシンプル。
O(N^3)でも意外と間に合うのね。