poj3254（状态压缩DP）

poj3254

题意

给出一个01矩阵，1表示当前这个位置可以放牛，要求放牛的方案保证牛不能左右或上下相邻，求方案数。

分析

dp[S][i]: 表示到 i 行时的状态S（用二进制数表示），那么状态转移就是 dp[S][i] += dp[S0][i - 1] ，其中 S 为当前行合法状态，S0为上一行的合法状态，且保证相邻两行同一列不能同时有 1 即可，对于当前行的所有有效状态枚举上一行的有效状态。因为 0 对于所有行而言都是有效状态，所以最后答案就是最后一行所有有效状态的方案数之和。

code

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int MAXN = (1 << 12) + 10;

const int MOD = 1e8;

int dp[MAXN][20];

int main() {

    int n, m;

    cin >> n >> m;

    dp[0][0] = 1;

    vector<int> vec1, vec2;

    for(int i = 0; i < n; i++) {

        int s = 0;

        for(int j = 0; j < m; j++) {

            int x;

            cin >> x;

            s += (1 << j) * x;

        }

        if(i) {

            for(int k = 0; k < (1 << m); k++) {

                if((s | k) == s && (k & (k >> 1)) == 0) {

                    for(int j = 0; j < vec1.size(); j++) {

                        if((vec1[j] & k) == 0)

                            dp[k][i] += dp[vec1[j]][i - 1];

                    }

                    vec2.push_back(k);

                }

            }

            vec1 = vec2;

            vec2.clear();

        } else {

            for(int k = 0; k < (1 << m); k++) {

                if((s | k) == s && (k & (k >> 1)) == 0) {

                    dp[k][i] = 1;

                    vec1.push_back(k); // 保存当前行所有有效状态，便于下一行直接枚举

                }

            }

        }

    }

    ll ans = 0;

    for(int j = 0; j < vec1.size(); j++) {

        ans = (ans + dp[vec1[j]][n - 1]) % MOD;

    }

    cout << ans << endl;

    return 0;

}

巴特西

poj3254（状态压缩DP）

poj3254

题意

分析

code

最新文章

热门文章