【POJ3254】Corn Fields（状压DP）

时间：2023-03-09 02:12:55
【POJ3254】Corn Fields（状压DP）

题意：

一个M x N矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，
可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。
问有多少种放牛方案(一头牛都不放也是一种方案)
(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)

思路：状压DP

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #define MOD 100000000

 #define N 12

 using namespace std;

 int dp[][<<];

 int a[];

 int b[<<];

 int n,m,x;

 int main()

 {

     freopen("poj3254.in","r",stdin);

     freopen("poj3254.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) a[i]=;

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

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

      {

        scanf("%d",&x);

        if(x==) a[i]+=(<<(j-));

      }

     int MAX=(<<m)-;

     for(int i=;i<=MAX;i++)

     {

         int x=i;

         b[i]=;

         while(x>)

         {

             if((x&==)&&((x>>)&==)) {b[i]=; break;}

             x>>=;

         }

     }

     for(int i=;i<=MAX;i++)

      if(!(i&a[])&&(b[i])) dp[][i]=;

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

      for(int j=;j<=MAX;j++)

       if((!(j&a[i]))&&(b[j]))

       {

           dp[i][j]=;

           for(int k=;k<=MAX;k++)

            if((!(k&a[i-]))&&(!(j&k))&&(b[k])) dp[i][j]=(dp[i][j]+dp[i-][k])%MOD;

       }

     int ans=;

     for(int i=;i<=MAX;i++)

      if ((!(i&a[n]))&&(b[i])) ans=(ans+dp[n][i])%MOD;

     printf("%d\n",ans);

     return ;

 }

相关文章