蒙德里安的梦想题目链接

291. 蒙德里安的梦想 - AcWing题库

蒙德里安的梦想题目类型

状态压缩DP+连通性

蒙德里安的梦想题目思路

核心：

先放横着的，再放竖着的

总方案数等于只放横着的小方块的合法方案数。

如何判断，当前方案是否合法

所有剩余位置，能否填充满竖着的小方块。可以按列来看，每一列内部所有连续的空着的小方块，需要是偶数个。

动态规划

• 状态表示：f[i, j]表示已经将前i-1列摆好，且从第i-1列，伸出到第i列的状态是j的所有方案。

• 状态计算

  • （1）(j & k)==0

  • （2）所有连续空着的位置的长度必须是偶数

蒙德里安的梦想代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
​
using namespace std;
​
const int N = 12, M = 1 << N;
​
int n, m;
long long f[N][M];
vector<int> state[M];
bool st[M];
​
int main()
{
    while(cin>>n>>m, n||m)
    {
        for(int i=0;i<1<<n;i++)
        {
            int cnt = 0;
            bool is_valid = true;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)
                {
                    if(cnt&1)
                    {
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt++;
            }
            if(cnt & 1) is_valid = false;
            st[i] = is_valid;
        }
        for(int i=0;i<1<<n;i++)
        {
            state[i].clear();
            for(int j=0;j<1<<n;j++)
                if((i & j)==0 && st[i|j])
                    state[i].push_back(j);
        }
        memset(f, 0, sizeof(f));
        f[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<1<<n;j++)
            {
                for(auto k: state[j])
                {
                    f[i][j]+=f[i-1][k];
                }
            }
        }
        cout << f[m][0] << endl;
    }
    return 0;
}