玉米地被别人收割了怎么办（Acwing 327. 玉米田）

算法分析

棋盘型状态压缩dp

这类dp有一个通用的状态表示法：f[i][j][k],表示前i行（放了j个棋子后）的状态表示为k    
    
    
。

由于本题无棋子要求    
    
    
，因此可以省去中间一维


     


     


     ，

即:

  用f[i][j]表示前i行土地的状态为j


     


     


     。

首先由于玉米地有不肥沃的地方不能种植
 




 




 



，因此需要通过二进制表示出来可以种植和不可以种植的地方   

   

   

，

我们是将整行用一个二进制数表示的 

     

     

    ，可种为0

  




  




  


，不可种为1  


  


  


，在输入的时候即可判断：

  g[i] += (!x<<(j-1)) //g[i]为每一行土地的二进制表示

由于是棋盘型  
     
     
   ，因此根据我们的经验显而易见可以知道需要分别分析棋盘的列和行：

根据题意相邻的两格内不能同时种玉米

可知：

  （以x为当前格）则  (x&x>>1)=0;

   这很容易理解


   




   




   

，比如x的二进制表示为1101 



 



 



，则x>>1 = 0110,可以得出x&x>>1的结果和题目要求相同；

再分析每一列               ，由于上下列不能同时种玉米：

  (y为相同列不同行的玉米地）因此(y&y-1)=0;

T.T好累

先看代码吧： #include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int N=13,mod = 1e8; int f[N][1<<N]; int g[N]; vector<int> state; vector<int> le_state[1<<N]; bool check(int x) { return !(x&x>>1); } int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x; scanf("%d",&x); g[i]+=(!x<<(j-1)); cout<<g[i]<<endl; } } for(int i=0;i<(1<<m);i++) { if(check(i)) { state.push_back(i); } } for(int i=0;i<state.size();i++) { for(int j=0;j<state.size();j++) { if(!(state[i]&state[j])) { le_state[i].push_back(j); } } } f[0][0]=1; for(int i=1;i<=n+1;i++) { for(int j=0;j<state.size();j++) { if(state[j]&g[i]) continue; for(int b=0;b<le_state[j].size();b++) { f[i][j] = (f[i][j] + f[i-1][le_state[j][b]])%mod; } } } cout<<f[n+1][0]; return 0; }