SRM523 Div1 Medium

500
メモ化する。
memo[h][w]=ベースの幅がwのブロックに高さhまでブロックを置くときのパターン数
ある幅を長さK以下のブロックで埋めようとしたとき、どれくらいのパターンがあるかを前もって計算しておく。

const int H = 50 + 1;
const int W = 50 + 1;
lli pattern[W];

lli memo[H][W];

const lli mod = 1000000007;

lli rec(int w, int h, const int k)
{
  if (h <= 0) return 1;
  if (w <= 0) return 1;
  if (memo[h][w] != -1) return memo[h][w];

  lli sum = (rec(w, h - 1, k) * pattern[w]) % mod;

  for (int b = 0; b < w; ++b) {
    lli s = rec(b, h - 1, k);
    lli t = pattern[b];
    lli u = rec(w - b - 1, h, k);
    sum += (((s * t) % mod) * u) % mod;
    sum %= mod;
  }
 
  return memo[h][w] = sum;
}

class BricksN {
public:
  int countStructures(int w, int h, int k)
  {
    fill(pattern, pattern + W, 0);
    pattern[0] = 1;
    for (int i = 0; i < W; ++i) {
      for (int j = 1; j <= k; ++j) {
        pattern[i + j] += pattern[i];
        pattern[i + j] %= mod;
      }
    }   

    fill(&memo[0][0], &memo[H - 1][W], -1);
    return rec(w, h, k);
  }
};