AtCoder ARC #104 : F - Visibility Sequence

これは時間さえあれば解けたな…。
https://atcoder.jp/contests/arc104/tasks/arc104_f

問題

N個のビルが左右一列に並んでいる。
各ビルiに対しP[i]とは、左側にある最寄りの自身より高いビルの番号を示す(存在しなければ-1)。

各ビルの高さは正整数で、その上限はX[i]とする。
数列Pとしてあり得るものは何通りか。

まず、一番左端に(-1に相当する)無限に高いビルがあるものとすると考えやすい。
また、X[i]は高々2N程度まで考えておけばよい。

i→P[i]の辺は互いに交差しない(P[i]＜P[j]＜i＜jとはなりえない)。
よってあるビルaに対し、P[i]、P[P[i]]、P[P[P[i]]]…がaとなるようなiは、a+1からある連続区間となる。

以下を考えよう。
f(L,R,H) := [L+1,R)の区間のビルiがすべてP[i]、P[P[i]]、P[P[P[i]]]…のどこかでLを含み、かつ高さがH以下であるようなPの組み合わせ
あとは解はf(-1,N,inf)となるので、これをメモ化再帰で解こう。

[L+1,R)の範囲でP[i]=Lとなる最後のiを総当たりしよう。
その時、[i+1,R]はmin(H,X[i])より低くなければならないので、
f(L,R,H) += f(L,i,min(H,X[i]))*f(i,R,min(H,X[i])-1)
と遷移する。

int N;
int X[101];
const ll mo=1000000007;
ll memo[205][205][205];


ll hoge(int L,int R,int H) {
	if(L==R) return 1;
	if(L+1==R) return 1;
	if(H<=0) return 0;
	if(memo[L][R][H]>=0) return memo[L][R][H];
	
	ll ret=0;
	for(int i=L+1;i<R;i++) {
		int nt=min(H,X[i]);
		(ret+=hoge(L,i,nt)*hoge(i,R,nt-1))%=mo;
	}
	
	return memo[L][R][H]=ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i+1];
		X[i+1]=min(200,X[i+1]);
	}
	X[0]=202;
	MINUS(memo);
	
	cout<<hoge(0,N+1,202)<<endl;
	
}

まとめ

一時期SRMでこういうの多かった印象。