TopCoder SRM 523 Medium BricksN

問題

1x1,1x2,...,1xkのブロックが無限にある。
これらのブロックを、1xwのブロックの上に積み上げる。

ただし、

  • 座標が整数でなくてはならない
  • 上のブロックは、下のブロックからはみ出てはならない
  • 高さは最大でh(土台は高さに含めない)

の条件を満たす必要がある。

ブロックの積み上げ方は何通りあるか、mod 10^9+7で求めよ。

制約条件

w,h,k≦50

方針

動的計画法による。
まず前計算で、1xiをブロックで隙間なく敷き詰める場合の数を求めておく。
これをnum[i]とする。


dp[w][h]を、幅w,高さhにブロックを(隙間があってもよい)敷き詰める場合の数とする。
すると、dp[w][h]は一列目を全てブロックで埋めた場合がまずdp[w][h-1]*num[w]通り
一列目の最初の隙間までのブロックがiとすると、
dp[w][h]+=dp[i][h]*num[i]+dp[w-i-1][h]
で、これを全てのiについて足し合わせればdp[w][h]が求まる。

ソースコード

const int mod=(int)1e9+7;
int dp[51][51],num[51];
int rec(int w,int h,int k){
	if(dp[w][h]>=0)return dp[w][h];
	int &ret=dp[w][h];
	if(w==0||h==0)return ret=1;
	ret=rec(w,h-1,k)*(ll)num[w]%mod;
	for(int i=0;w-i-1>=0;i++)ret=(ret+(ll)num[i]*rec(i,h-1,k)%mod*rec(w-i-1,h,k)%mod)%mod;
	return ret;
}
class BricksN {
	public:
	int countStructures(int w, int h, int k) 
	{
		memset(num,0,sizeof(num));
		num[0]=1;
		for(int i=1;i<=50;i++)for(int j=1;j<=min(i,k);j++)num[i]=(num[i]+num[i-j])%mod;
		memset(dp,-1,sizeof(dp));
		return rec(w,h,k);
	}
};