既出問題だったのでコピペで解いてしまいました。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_g
問題
1~Nの番号が振られた木を成す無向グラフがある。
1番の頂点から初めて、隣接する未到達の点のうち最小値のところにDFSで移動する、という作業を繰り返し木を探索する。
N個の頂点の初訪問の順番が与えられるとき、そのような訪問順となるグラフの組み合わせ数を求めよ。
解法
完全に既出です。本番もこのコードを少し直して通しました。
Codeforces #289 Div2 F. Progress Monitoring - kmjp's blog
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; string s; cin>>N; FOR(i,N) cin>>B[i], B[i]--, sp[i][i]=sub[i][i]=1; if(B[0]!=0) return _P("0\n"); for(int 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; }
解法
既出でなければ多分時間内に解けなかった。
みんなよくこれ本番通すな…割とよくあるテクなのかな?