SRM523 Div1 Medium

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

view plainprint?

1. const int H = 50 + 1;  
2. const int W = 50 + 1;  
3. lli pattern[W];  
4.   
5. lli memo[H][W];  
6.   
7. const lli mod = 1000000007;  
8.   
9. lli rec(int w, int h, const int k)  
10. {  
11.   if (h <= 0) return 1;  
12.   if (w <= 0) return 1;  
13.   if (memo[h][w] != -1) return memo[h][w];  
14.   
15.   lli sum = (rec(w, h - 1, k) * pattern[w]) % mod;  
16.   
17.   for (int b = 0; b < w; ++b) {  
18.     lli s = rec(b, h - 1, k);  
19.     lli t = pattern[b];  
20.     lli u = rec(w - b - 1, h, k);  
21.     sum += (((s * t) % mod) * u) % mod;  
22.     sum %= mod;  
23.   }  
24.    
25.   return memo[h][w] = sum;  
26. }  
27.   
28. class BricksN {  
29. public:  
30.   int countStructures(int w, int h, int k)  
31.   {  
32.     fill(pattern, pattern + W, 0);  
33.     pattern[0] = 1;  
34.     for (int i = 0; i < W; ++i) {  
35.       for (int j = 1; j <= k; ++j) {  
36.         pattern[i + j] += pattern[i];  
37.         pattern[i + j] %= mod;  
38.       }  
39.     }     
40.   
41.     fill(&memo[0][0], &memo[H - 1][W], -1);  
42.     return rec(w, h, k);  
43.   }  
44. };  

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