算法板子

// f[i][j] 前 i - 1 列铺满,j 以二进制形式表示第 i 列有值得情况(横着排支出来的情况)
#include<bits/stdc++.h>
using namespace std;
const int N = 2048 + 10;
typedef long long LL;
LL f[15][N];
vector<int> p[N];
int n, m;
int main() {

    cin >> n >> m;
    while (n != 0 && m != 0) {
        for (int i = 0; i < (1 << n); ++i) {
            p[i].clear();
            for (int j = 0; j < (1 << n); ++j) {
                if (i & j) continue;
                bool valid = true;
                int cnt = 0;
                for (int k = 0; k < n; ++k) {
                    if (i & (1 << k) || j & (1 << k)) {
                        if (cnt & 1) {
                            valid = false;
                            break;
                        }
                        cnt = 0;
                    } else {
                        ++cnt;
                    }
                }
                if (cnt & 1) {
                    valid = false;
                }
                if (valid) {
                    p[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 : p[j]) {
                    f[i][j] += f[i - 1][k];
                }
            }
        }
        cout << f[m][0] << endl;
        cin >> n >> m;
    }
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/state-compression-dp/
最后修改日期:2020年6月21日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。