题目链接

  • 思路分析：显然是道动态规划的题目。首先考虑的是对当前矩形左下角的第一块方格所属的砖的类型进行讨论，分割状态空间，但是写完后发现与答案有所出入。在对样例(2， 2， 2)进行逐个分析后，发现确实漏情况了，即下面两块分散的砖上层可以用同一块砖，这种情况把刚才的思路否定掉了。
    然后通过参考别人的AC代码学习，发现正确思路应该是对当前矩形左下角的第一个连续段的长度进行讨论。这样就巧妙地利用了题目中任意砖下不为空的约束条件(连续段的空格处正确地分割子问题)。这样，一个左下角的连续段就把当前矩形分割成了三部分：连续段(i * 1)、连续段上方矩形(i * (h-1))、连续段右方隔至少一个间隔的矩形((w-i-1) * h)，且三者相互独立，至此问题得到解决。

  • 实现代码：

    #include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int mod = 1e9 + 7;  // int占4个字节，首位为符号位，0~30位表示的最大值为2^31-1 = 2.1e9
const int N = 50 + 5;

// 在1*1*k的长度中，铺砖的方案，砖长从0到k
ll brick[N];
ll wh[N][N];

int k;
// 在1*1*w的区域中，首格开始连续的长度为w，返回方案数
ll calBrick(int w) {
  ll &t = brick[w];
  if (t >= 0) return t;
  if (w <= 0) return 1;

  t = 0;
  // i不等于0，则通过递归可知，1*1*w的区域被填满
  for (int i = 1; i <= w && i <= k; i++) {
      t = (t + calBrick(w - i)%mod)%mod;  //在1*1*w的区域中，区域首块被砖长为i的砖所占据
  }
  return t;
}

ll solve(int w, int h) {
  // 以防数组越界
  if (w <= 0 || h <= 0) return 1; 
  ll &t = wh[w][h];
  if (t >= 0) return t;

  // 因为w=1,h=1均是合法值，且下方有w-1,h-1，因此边界应该为0
  // 边界值的规定，可通过特殊值法来确定，如solve(10, 1), solve(1, 10)
  t = 0;
  for (int i = 0; i <= w; i++) {
      t = (t + (calBrick(i) * (solve(i, h - 1)%mod * solve(w - i - 1, h)%mod)%mod)%mod)%mod;  //在w*h的区域中，左下角的区域从首格开始的连续段长为i,w-i-1以保证不连续
  }

  return t;
}
int main() {
  int w,h;
  cin >> w >> h >> k;

  memset(brick, -1, sizeof(brick));
  // 二维数组也可以使用memset置初值-1
  memset(wh, -1, sizeof(wh));

  cout << solve(w, h) << endl;
  return 0;
}