最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天新动态：AcWing291.蒙德里安的梦想题解

来源：博客园

题解：蒙德里安的梦想

注：

本题解内容简陋，多有不周，敬请谅解。如果有问题请在评论区留言。谢谢。由于作者能力有限，这篇题解不会给出太严谨的证明，只是旨在帮助大家更好地理解此题，具体的做法请读者自己思考。

题目简述:

求把 \(N×M\) 的棋盘分割成若干个 \(1×2\) 的长方形，有多少种方案。


【资料图】

如下图所示：

当 \(N=2,M=4\) 时，共有上图所示的五种方案

解题大概思路

首先，对于方案数的计算，可以考虑搜索枚举以计算答案。但是，考虑到搜索的复杂度是指数级别的（很抱歉，这里没能够想出复杂度是多少，如果有同学计算出来了可以在评论区留言），不能够通过 \(N \leq 11\) 的数据范围。于是我们需要考虑优化搜索算法。

如果大家看过闫老师的 \(DP\) 问题分析课，就会发现 \(DP\) 实际上就是对搜索的优化（其中一种实现方式就是记忆化搜索）。所以，对于这一道题，我们可以考虑使用动态规划算法来解决。

闫氏 \(DP\) 分析法主要分为两大步骤：状态表示和状态计算。在大概思路里我们只讨论状态表示。我们考虑一列一列地放置长方形（我也不清楚为什么要这样表示状态，暂时将其理解为这种 棋盘式动态规划问题的一种套路）。那么，某一列放置的方案只与上一列的放置方案有关（至于为什么接下来会进行详细说明）。为了方便记录状态，我们考虑使用状态压缩的方式存储状态。于是就有了本题的大概思路：状态压缩动态规划。

算法设计

我们考虑使用闫氏 \(DP\) 分析法来解决此题：

以上的描述可能过于模糊。我们来举一个例子看一看：

左侧表示状态 \(f[2][0]\) （请注意，我们行和列的编号都从 \(0\) 开始，二进制表示第 \(0\) 行为 \(2^0\) ，第 \(i\) 行为 \(2^i\) ），它可以从右侧（可能不只）的三个状态转移过来: \(f[1][4],f[1][7],f[1][1]\) 。

那么如何判断一个状态 \(f[i][state]\) 是否可以由状态 \(f[i-1][j]\) 转移而来呢？

结论是，当且仅当以下条件成立:

  1. \(state ~ \& ~ j = 0\)
  2. \(state ~ | ~ j\) 每一段连续的 \(0\) 都是偶数个

接下来我们来不严谨地粗略证明以下以上结论。

我们要证明的命题是，\(j\) 状态可以由 \(state\) 状态演变而来，并且有且仅有一种演变方案，当且仅当我们说到的上述条件成立。即

\[j状态可以由state状态演变而来，并且有且仅有一种演变方案\Leftrightarrow 上述条件成立\]

我们需要证明以下命题：

\[\tag{1}j~状态可以由~state~状态演变而来，并且有且仅有一种演变方案\rightarrow 上述条件成立\]\[\tag{2}j~状态可以由~state~状态演变而来，并且有且仅有一种演变方案\leftarrow 上述条件成立\]

我们先证明命题 \((1)\) ：

如果说 \(j\) 状态可以由 \(state\) 状态演变而来，并且有且仅有一种演变方案，那么上述条件成立.

我们先说一说 \(state~\&~j = 0\) 等价于什么。这等价于 \(state\) 和 \(j\) 不能在同一位上同时都是一（这里就不给出严格证明了）。我们又可以知道，状态上某一位为一，意味着这一位对应的方格放置的是一个横向的小长方形（这里也不给出严格证明，读者可以自己想想为什么）。也就是说， \(state~\&~j = 0\) 保证了两个小方块重叠的情况不会发生。我们可以大概感受一下，如果说 \(j\) 状态可以由 \(state\) 状态演变而来，那么重叠的情况是不会发生的。

我们再说一说 \(state~|~j\) 代表着什么。 \(state~|~j\) 上某一位为零等价于 \(state\) 和 \(j\) 在这一位上都不为零，也就等价于这一位上没有摆放长方形。我们考虑先摆放横着的长方形再摆放竖着的长方形，那么如果连续的 \(0\) 是奇数个，我们从感觉上可以感知到这种情况是不可能用竖着的小方块铺满的（这里也不给出严格证明）。所以说，如果说命题 \((1)\) 是成立的。

我们再来证明命题 \((2)\) ：

如果上述条件成立，那么存在且仅存在一种摆放横向小方格的方式，并且剩余部分可以由纵向的小方格铺满，并且纵向摆放的方式也有且仅有一种（感觉上应该是这样的），那么 \((2)\) 也是成立的。

于是对于某一个状态 \(state\) ，我们可以枚举每一个状态 \(j\) ，如果说 \(state\) 和 \(j\) 满足以上条件，那么 \(f[i][state]\)+=\(f[i-1][j]\)

完整代码

代码如下：

#include#include#include#include#define f_inline inline __attribute__((always_inline))using namespace std;using UL=unsigned long;using ULL=unsigned long long;//用于存储大型非负整数bitset<2050> isValid;vector
     partner[2050];//partner[i]存储i所对应的合法的状态ULL f[15][2050];f_inline bool check(register const UL num,register const UL N)//i是一个N位二进制数,返回值等价于num是否合法，即所有连续的0都是偶数个{    register UL cnt(0);    for(register UL i(0);i>i)&1)        {            if(cnt&1)                return false;            cnt=0;        }        else            ++cnt;    return !(cnt&1);}int main(){    register UL N,M;    while(cin>>N>>M,N||M)    {        register const UL bound(1<::iterator it(partner[j].begin());it!=partner[j].end();++it)                        f[i][j]+=f[i-1][*it];        cout<

关键词： 有且仅有 演变而来 蒙德里安