poj 3254 状态压缩dp 放牧~

末蓝、 2022-08-18 12:20 185阅读 0赞

Corn Fields

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 10821</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 5668</td> 
  </tr> 
 </tbody> 
</table>

Description

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

题意:草场中有肥沃的地方,也有贫瘠的地方,John要在肥沃的地方放牛,要求就是每只牛的相邻位置不能有别的牛,求所有的安排方案总数.

分析:写的第一个状态压缩dp,参考了别人的代码.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=1<<12+3;
    int state[N],a[N];
    int dp[12][N];
    
    inline bool CanBeState(int i)
    {
        return !(i&(i>>1));//如果有连续的两个1,那么右移一位与原先的值相与肯定是1
    }
    inline bool ok(int x,int y)
    {
        return !(a[x] & state[y]);  //地图a中所有不能放牛的地方都被设置成1了,如果当前状态在不能放牛的地方
                                    //是1,那么相与肯定是1
    }
    
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    int x=in();
                    if(!x)
                    {
                        a[i] += 1<<j;
                    }
                }
            }
            int total=0;
            for(int i=0;i<(1<<m);i++)
            {
                if(CanBeState(i)){
                    state[total++]=i;  //所有的状态在这里
                }
            }
            for(int i=0;i<total;i++){   //先把第一行的算出来
                if(ok(0,i)){
                    dp[0][i]=1;
                }
            }
            for(int i=1;i<n;i++)   //从第二行开始
            {
                for(int j=0;j<total;j++){   //对每一行枚举每个状态
                    if(!ok(i,j)) continue;   //当前这个状态与地图中的情况不符
                    for(int k=0;k<total;k++){  //当前的状态符合,再枚举前一行的每一个状态,如果前面一行的某一个符合前一行的状态并且
                                                //也跟当前的状态相符(即同位置不能有1),那么进行状态转移.
                        if(!(ok(i-1,k))) continue;
                        if(state[k] & state[j]) continue;  //同位置不能有1
                        dp[i][j] += dp[i-1][k];  //状态转移
                    }
                }
            }
            int ans=0;
            for(int i=0;i<total;i++){
                ans=(ans+dp[n-1][i])%100000000;
            }
            cout<<ans<<endl;
            mem(dp,0);       //不要忘记初始化
            mem(a,0);
    
        }
        return 0;
    }