0

我正在尝试在SPOJ GNY07H上解决这个问题：问题是：

我们希望将一个 4 个单位高、N 个单位长的网格与 2 个单位的矩形（多米诺骨牌）平铺一个单位（在任一方向上）。

编写一个程序，将网格的宽度 W 作为输入，并输出平铺 4×W 网格的不同方式的数量。

输入：2 3 7

输出：5 11 781

我知道这是一个位掩码动态编程问题。但是，我的方法没有得到正确的输出。谁能指出我的方法中的错误。

这是代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

int dp[16][4][60];

int solve(int mask, int d, int t)
{
    if(t > 4)   return 0;
    if(d == 0)  return mask == 0;
    if(t == 4)  return solve(mask, d-1, 0);
    int &ret = dp[mask][t][d];
    if(ret != -1)
        return ret;
    ret = 0;
    ret += solve(mask|(1<<t), d, t+1) + solve(mask, d, t+2);
    return ret;
}

int main()
{
    int i, j, k, l, n, w;

    scanf("%d", &n);

    while(n--)
    {
        memset(dp, -1, sizeof(dp));
        scanf("%d", &w);
        int ans = solve(0, w, 0);
        printf("%d\n", ans);
    }
    return 0;
}

该方法的工作原理如下：

我一行一行地工作。在每一行，对于一列，我尝试先水平和垂直放置瓷砖。mask属性告诉行+1 中已经填充了哪些列。因此，当平铺在行中水平放置时，掩码=掩码| (1 << column ( t )) 用于第 1 行，否则保持不变。我以这种方式计算可能性的总数。递归的停止条件是当行（在程序中为d）时掩码为 0 时，即行变为 0。当此级别的所有列都被填满时，我们减少行（ d ）。

4

1 回答 1

0

我没有花时间完全理解这个问题，但只是看一下代码，这看起来像是一个没有计算的缓存机制。在主循环的每次迭代中，您将缓存设置dp为全 -1，但在其他任何地方都没有将其内容设置为其他任何值。然后在 中solve()，您有一些返回 0 的特殊情况，然后是返回几个递归调用之和的主要情况；但是这些递归调用也无法合法地返回零以外的任何值。

似乎缺少两件事solve()：

  1. 一种极限情况，对于 d、t 和 mask 的某些值，非递归计算数值；和
  2. 在某些时候，计算的值应该存储在dp.

另外，我认为缓存dp可能应该在循环之外main()被清除，尽管我不是 100% 确定这一点。

于 2013-09-03T10:44:13.987 回答