AtCoder ABC #252 : G - Pre-Order

これは似たようなの見たことある気がする。
https://atcoder.jp/contests/abc252/tasks/abc252_g

問題

頂点に1～Nのラベルがついた、頂点1を根とする根付き木がある。
この頂点をDFSして行きがけ順にラベル番号を並べたところ、数列Pを得た。
(なお、各頂点から子頂点に移動する際は、ラベルの小さい順に移動する)

数列Pを得られるような木は何通りか。

解法

以下を考える。
f(L,R) := 区間[L,R)に対し、P[L]を根とし、その下にP[L+1]…P[R-1]の頂点がぶら下がるような、条件を満たす木の総数
g(L,R) := 区間[L,R)に対し、P[L]...P[R-1]のうちいくつかラベルが昇順になる点を根とし、それぞれ順にDFSすると、P[L]...P[R-1]を得られるような木の総数

f(0,N)が求めたい値である。

• f(L,R)は、ラベルP[L]の下にいくつかの木をぶら下げるので、f(L,R) = g(L+1,R)
• g(L,R)は、P[L]...P[M-1]が1つの根付き木になるケースを考えると、P[L]＜P[M]である場合g(L,R) += f(L,M)*g(M,R)

上記gの計算は状態はO(N^2)通りで、そこからMの選び方がO(N)通りあるので、全体でO(N^3)で解ける。

int N;
const ll mo=998244353;
int P[505];

ll F[505][505];
ll G[505][505];


ll par(int L,int R);

ll top(int L,int R) {
	if(L+1>=R) return 1;
	if(F[L][R]>=0) return F[L][R];
	return F[L][R]=par(L+1,R);
}
ll par(int L,int R) {
	if(L+1>=R) return 1;
	if(G[L][R]>=0) return G[L][R];
	
	ll ret=top(L,R);
	for(int i=L+1;i<R;i++) if(P[L]<P[i]) (ret+=top(L,i)*par(i,R))%=mo;
	return G[L][R]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	MINUS(F);
	MINUS(G);
	cout<<top(0,N)<<endl;
}

まとめ

どこで見たんだっけかな。