poj 3154 Corn Fields-白红宇

poj 3154 Corn Fields

阅读量：4114 次

发布时间：2019-05-25

本文共 1438 字，大约阅读时间需要 4 分钟。

题意：有n行m列的矩阵，只能有0和1两种数字，现在准备在矩阵上放母牛（只能放在1上），问有多少种分配方案，

使得没有牛相邻。

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; const int mod=100000000; int max(int a,int b) {return a>b?a:b;}; int min(int a,int b) {return a
               
                >1)||j&(j<<1)) continue;//枚举的j没有1相邻 for(int k=1;k<=m;k++) if(!fi[i][m-k+1]&&((j>>(k-1))&1)) { flag=0; break; }//枚举的j不与矩阵冲突 if(!flag) continue; //cout<<"2\n"; for(int k=0;k<=(1<

分析：dp[i][j]扫到第i层选取状态为j时的状态数，dp[i][j]+=dp[i-1][k]（k为前一行符合要求的状态）

扫到第i行时，枚举当前状态，再枚举前一状态，要是符合要求的话就相加

wa代码：

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; const int mod=100000000; int max(int a,int b) { return a>b?a:b;}; int min(int a,int b) { return a
               
                >1)||j&(j<<1)) continue; for(int k=1;k<=m;k++) if(!fi[i][k]&&((j>>(k-1))&1)) { flag=0; break; } if(!flag) continue; for(int k=0;k<=(1<