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); } };