POJ 3254(动态规划-状压dp）

短命女 2022-06-01 02:49 135阅读 0赞

问题描述:

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

Line 1: Two space-separated integers: M and N   
Lines 2.. M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

Sample Input

2 3
    1 1 1
    0 1 0

Sample Output

题目题意:给我们一个01矩阵，1的位置可以种玉米，但是俩块玉米地不能相连，问有多少种情况，其中不种玉米也算一种

题目分析:考虑到每一行（只有12位）完全可以用状压表示出所有情况，转移到下一行好办，只需要判断下一行的这个状态与上一个状态相与为0，上下就肯定不相连了，但是同一行就非常麻烦了，所以要预先处理出每一行存在的所以情况

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #define ll long long
    using namespace std;
    
    vector<int> vec;
    const ll mod=100000000;
    int dp[15][(1<<12)];
    int G[15][15];
    
    void init()
    {
        for (int i=0;i<(1<<12);i++) {
            if ((i&(i<<1))==0) vec.push_back(i);
        }
    }
    bool check(int x,int n)
    {
        for (int i=0;i<=12;i++) {
            if ((n&(1<<i))) {
                if (!G[x][i+1]) return false;
            }
        }
        return true;
    }
    int main()
    {
        int n,m;
        init();
        while (scanf("%d%d",&n,&m)!=EOF) {
            memset (G,0,sizeof (G));
            for (int i=1;i<=n;i++) {
                for (int j=1;j<=m;j++) {
                    scanf("%d",&G[i][j]);
                }
            }
            memset (dp,0,sizeof (dp));
            dp[0][0]=1;
            for (int i=1;i<=n;i++) {
                for (int j=0;j<vec.size()&&vec[j]<(1<<m);j++) {
                    if (!check(i,vec[j])) continue;//判断当前状态下的位置是否都能种玉米
                    for (int k=0;k<vec.size()&&vec[k]<(1<<m);k++) {
                        if ((vec[j]&vec[k])==0) {//相与为0
                            dp[i][vec[j]]+=dp[i-1][vec[k]];
                        }
                    }
                }
            }
            ll ans=0;
            for (int j=0;j<vec.size()&&vec[j]<(1<<m);j++) {
                    ans=(ans+dp[n][vec[j]])%mod;
            }
            printf("%lld\n",ans%mod);
        }
        return 0;
    }