TopCoder SRM 523 Div1 Medium BricksN

これはDiv2 Hardを解いていたのですんなり。
http://community.topcoder.com/stat?c=problem_statement&pm=11616

問題

幅Wの土台がある。ここに高さ1、幅1～Kのブロックを最大高さHに達するまで積んでいきたい。
なお、各ブロックの下には他のブロックがなければならず、空中に浮くような配置をしてはならない。

W,H,Kに対し、ブロックの配置の組み合わせ数を答えよ。

解法

まずDPで連続する幅xを埋める埋め方を求める。以後これを一塊のブロックとみなす。

次に、Wの土台上にその幅1～Wの塊を置くDPを行っていく。
各塊の間を1マス以上の隙間を空けて左からおいていけばよい。

ll mo=1000000007;

class BricksN {
	public:
	int K;
	ll line[51];
	ll memo[51][51][2];
	
	ll dodo(int W,int H,int first) {
		if(H<=0) return first;
		if(W<=0) return 0;
		if(memo[W][H][first]>=0) return memo[W][H][first];
		int x,w,x2;
		
		if(first==1) {
			memo[W][H][first]=1;
			FOR(x,W) for(w=1;w<=W-x;w++) {
				ll ret=line[w]*dodo(w,H-1,1)%mo;
				ll tot=1;
				for(x2=x+w+1;x2<W;x2++) tot+=dodo(W-x2,H,0);
				tot%=mo;
				memo[W][H][first]+=ret%mo*tot%mo;
			}
		}
		else {
			memo[W][H][first]=0;
			for(w=1;w<=W;w++) {
				ll ret=line[w]*dodo(w,H-1,1)%mo;
				ll tot=1;
				for(x2=w+1;x2<W;x2++) tot+=dodo(W-x2,H,0);
				tot%=mo;
				memo[W][H][first]+=ret%mo*tot%mo;
			}
		}
		memo[W][H][first] %= mo;
		return memo[W][H][first];
		
	}
	
	int countStructures(int w, int h, int k) {
		K=k;
		int i,j;
		
		MINUS(memo);
		ZERO(line);
		line[0]=1;
		FOR(i,w) for(j=1;j<=k;j++) {
			if(i+j<=w) line[i+j]=(line[i+j]+line[i]) % mo;
		}
		
		return dodo(w,h,1);
	}
};

まとめ

割とオーソドックスなDP+メモ化再帰。