小白向

动态规划

• 状态表示
• 设状态f[i, j]，第i列的状态为j，解释一下j这个状态，代表第i-1列凸过来的方块，有即是1，无即是0，为什么要这样表示，因为无非就两种情况，有与无，其他的表示都挺麻烦的，你用字符串？抽出来未免也太麻烦了
• 集合
  • 以第i列为最终边界的所有可行方法
• 属性
  • 数量
• 状态计算
• 枚举前一列状态为为k
  • 首先，枚举我们这一列的时候，不能和前面的矛盾，i列与i-1列不能和i-2与i-1列达到重叠
  • j&k==0
  • 不重叠！妙啊！重叠就是1
  • 其次，横向的枚举完了，剩下的得能竖向放进去，即不能存在连续计数个0
  • j|k，这样其中0的位置就是i-1列中空方格的位置
  • 预判断出来判断这种状态是否合法
• 当两个条件能够满足，就代表可以转移而来f[i][j]+=f[i-1][k]

代码实现

#include <iostream>
#include <cstring>

using namespace std;

//M就是2的N次方 每一行都有0与1这两种状态
const int N = 12, M = 1 << N;

long long f[N][M];
//用来预处理状态的可行性
bool st[M];

int main() {
    int n, m;

    //,运算符   返回第二个操作数   只要n和m不同时为0即可
    while (cin >> n >> m, n || m ) {
        //每一轮都要重新开始啦~至于st数组,我们数组里每次都会覆盖的,不用在这里写了
        memset(f, 0, sizeof f);

        //查看每一种状态
        for (int i = 0; i < 1 << n; i ++ ) {
            st[i] = 1;
            //记录连续的0的个数
            int cnt = 0;
            for (int j = 0; j < n; j ++ ) {
                //i>>j即第j+1行,数据是1就代表着这里有方块,不是0,说明分割出来了
                if (i >> j & 1) {
                    //由于达到了分割的效果,我们看看上一轮是不是奇数个0
                    if (cnt & 1) {
                        //奇数个0直接over啦
                        st[i] = 0;
                        cnt = 0;
                    }
                } else cnt ++;
            }
            //看一下最后的一次 因为循环内可能没有分割到就结束了
            if (cnt & 1) {
                st[i] = 0;
            }
        }

        //dp
        //第1行前一行肯定没东西啊,所以只有全为0是一种情况
        //边界条件处理
        f[0][0] = 1;

        //正式dp
        //注意等于号 后面解释
        for (int i = 1; i <= m; i ++ ) {
            //枚举这一行和前一行的所有状态数目
            for (int j = 0; j < 1 << n; j ++ ) {
                for (int k = 0; k < 1 << n; k ++ ){
                    //满足我们分析的条件即可
                    if ((j & k) == 0 && st[j | k]) {
                        f[i][j] += f[i - 1][k];
                    }
                }
            }
        }
        //答案为什么存在这里呢？结束之后我们m行应该是刚刚好全部塞满
        //所以第m+1行应该啥也没有了
        cout << f[m][0] << endl;
    }

    return 0;
}