09月18, 2016

POJ2411多米诺骨牌完美覆盖(状压DP 轮廓线DP)

Mondriaan’s Dream(POJ2411多米诺骨牌完美覆盖)

Time Limit:3000MS Memory Limit:65536KB 多米诺骨牌完美覆盖是组合数学中经典的题目,要求对给定长宽的区域求用1 * 2的矩形完美覆盖的方案总数。

整行状态考虑

仔细思考可以发现,每一行的可行方案数与上一行的排列方式有关。如果上一行在此列竖直放置了一个矩形,这这一行的此列就不能放置任何矩形了。想到这一点我们自然会想到用DP来处理此题,DP的状态可以用两个参数标识,分别是当前的行数,当前行的方案。 DP过程中可以dfs遍历当前行所有的下一行可行方案,母状态方案数为所有子状态方案数之和。dfs终点时检验状态是否有效,即小矩形是否出界。 可先枚举出所有可以衔接的两行的情况,缩小dfs遍历范围。 对两行的每列操作,可以发现一共存在3种操作(第三种有两种表现形式)。

每一格可以按是否受上一行影响分别用0、1标号,如上图所示,被影响标号为1,未被影响标号为0。也可以反向标号,但后面要用到的递推状态、起始状态和终点状态则不同。 现在,我们可以dfs枚举出所有情况,代码为反向标号

vector<int> mp[MAXN];
void dfs1(int p, int s1, int s2) 
//horizen 1, vertical 1 0, or , affected by last row 0, otherwise 1
{
    if (p > m) return;
    if (p == m) {
        mp[s1].push_back(s2);
        return;
    }
    dfs1(p + 1, s1 << 1 | 1, s2 << 1);    //pic 3
    dfs1(p + 1, s1 << 1, s2 << 1 | 1);
    dfs1(p + 2, s1 << 2 | 3, s2 << 2 | 3);    //pic 1
}

这里使用类似临接表的存储方法,存下所有可以衔接的状态。 接下来就可以进行DP了

dfs做法

ll dfs2(int pos, int s)
{
    if (pos == n ) {
        if (s == (1 << m) - 1) return 1; //此处受状态不同影响
        return 0;
    }
    if (~dp[pos][s])
        return dp[pos][s];
    ll ans = 0;
    for (int i = 0; i < mp[s].size(); i++)
        ans += dfs2(pos + 1, mp[s][i]);
    return dp[pos][s] = ans;
}
cout << dfs2(0, (1 << m) - 1) << endl; //此处受状态不同影响

循环转移做法

dp[n][(1 << m) - 1] = 1; //此处受状态不同影响
for (int i = n - 1; i >= 0; i--)
    for (int j = 0; j < (1 << m); j ++)
        if (dp[i + 1][j])
            for (int k = 0; k < mp[j].size(); k++)
                dp[i][mp[j][k]] += dp[i + 1][j];
cout << dp[0][(1 << m) - 1] << endl; //此处受状态不同影响

一些小细节

while (cin >> n >> m && n + m) {
    if ((n * m) & 1) {
        puts("0");
        continue;
    } //面积为奇数时显然不能完美覆盖
    init();
    if (m > n) swap(m, n); //尽量减少可行的方案数

轮廓线DP做法

本题可以说是最经典的轮廓线dp问题。白书上有完整题解,但有些地方较为难懂,有一处私以为有误。(图6-3往左情况k4=1) 具体做法是模拟轮廓线的变化,从最开始的一格往后递推,每时刻记录完整一行的状态。作为白书上解法的一个梳理,我们按照从上到下、从左到右把nm的棋盘分割成nm个阶段,显然,每个阶段只与上一个阶段有关。使用二进制进行状态压缩,0表示未被覆盖,1表示已被覆盖。 每次我们只决定当前最新的这一格的骨牌怎样放置,可以影响到当前轮廓线上其他格,但不能影响到下一格或以后的格子(下一格和以后格子的人生让它自己决定)。 所以,对每一格,我们有且只有三种摆放方式

  1. 不放(就是这么任性)
  2. 向左放(影响左边的一格)
  3. 向上放(影响上面的一格)

可以发现,决定完当前格,当前格上面的那一格(不是上一格,上一格其实是左边的一格)如果还没有被覆盖,就再也没有被覆盖的机会了。我们不能让这样的情况发生(因为这是不符合题意的),所以如果当前格的上面一格还未被覆盖的话,1.不放 和 2.向左放 都是invalid,我们只能 3.向上放。 现在可以写出以下代码

void update(int 新的状态,int 旧的状态)
    if(旧的状态里要消失的那个一格还没被覆盖) return;
    else d[cur][新的状态] += d[cur^1][旧的状态];

代码中的cur在0和1之间变化,只为区分此阶段和上一阶段,因为两个阶段可能有相同的状态,不区分会混乱。 然后可以写出三种操作的代码 不放

update(k, k << 1);

向上放(上覆盖)

if (i) // && !(k & (1 << m - 1))
          update(k, (k << 1) ^ (1 << m) ^ 1);

此处用 ^ 和 | 的区别留给读者思考(hint:与update和注释里的语句有关) 向左放(左覆盖)

if (j && !(k & 1)) update(k, (k << 1) ^ 3);

左覆盖需要左边原本没有覆盖 附AC代码

typedef ll long long;
int n, m, cur;
const int maxn = 15;
ll d[2][1 << maxn], memo[maxn * maxn][maxn * maxn];
// 1为已覆盖,0为未覆盖
void update(int a, int b)
{
  if (b & (1 << m)) // 最旧的一格必须已被覆盖
    d[cur][b ^ (1 << m)] += d[1 - cur][a];
}

ll solve(int n, int m)
{
  memset(d, 0, sizeof(d));
  cur = 0;
  d[0][(1 << m) - 1] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) { // 枚举当前要算的阶段
      cur ^= 1; // 只区分当前阶段与上一阶段
      memset(d[cur], 0, sizeof(d[cur]));
      for (int k = 0; k < (1 << m); k++) { // 枚举上个阶段的状态
        update(k, k << 1); //不放
        if (i&& !(k & (1 << m - 1))) // 上覆盖
          update(k, (k << 1) ^ (1 << m) ^ 1);
        if (j && !(k & 1)) // 左覆盖
          update(k, (k << 1) ^ 3);
      }
    }
  return d[cur][(1 << m) - 1];
}

int main()
{
  memset(memo, -1, sizeof(memo));
  while (scanf("%d%d", &n, &m) == 2 && n + m) {
    if (n < m) swap(n, m);
    if (memo[n][m] < 0) memo[n][m] = solve(n, m);
    printf("%lld\n", memo[n][m]);
  }
  return 0;
}

To sum up

通过细想这个经典题目的两种做法,我们可以浅探状压DP和轮廓线DP。还记得在第一种做法时,我们用一个dfs,预处理出了所有可以衔接的情况,这其实就是对轮廓线的一种枚举。而在后一个做法中,我们其实是在遍历的过程中不断发展轮廓线。前者的时间复杂度是O(Nm),N为列数为m时可能轮廓线的数目,后者的时间复杂度O(2mmn),两者m都取行数和列数的较小值。 ps:作为一个经典的组合数学问题,伟大的数学家们早已总结出了公式。。 [latex] \prod {i=1}^{\frac{n}{2}}\prod {j=1}^{\frac{m}{2}}\left [ 4\cos ^{2}\left ( \frac{i\pi }{n+1} \right ) + 4\cos ^{2}\left ( \frac{j\pi }{m+1} \right )\right ] [/latex] 有了公式还写不出代码?悲剧的是POJ卡精度,我这样写的话eps=1e-3是能AC的 附AC代码

#define PI acos(-1.0)
#define eps 1e-3
double fuck(double a, double b)
{
    return cos(a * PI / (b + 1)) * cos(a * PI / (b + 1)) ;
}
int main()
{
    int n, m;
    while (cin >> n >> m && n + m) {
        if ((n & 1) && (m & 1)) {
            puts("0");
            continue;
        }
        double ans = 1;
        for (int i = 1; i <= n / 2; ++i) {
            for (int j = 1; j <= m / 2; ++j) {
                ans *= 4 * (fuck(i, n) + fuck(j, m));
            }
        }
        cout << (ll)(ans + eps) << endl;
    }
}

”可恶,我们辛辛苦苦算出来的和他们猜出来的是一样的。“ —— 某数学系生

本文链接:https://sxing.xyz/post/poj2411多米诺骨牌完美覆盖状压dp-轮廓线dp.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。