[关闭]
@Acqua 2019-01-27T13:11:43.000000Z 字数 1085 阅读 978

POJ3254 Corn Fields（Jan. 27th, 2019） 状压DP

动态规划

题目来源

题意

给定一个的棋盘，要在矩阵中放置棋子。每行有位置不能放，且上下左右不能相邻放置。求放置方案数。

思路

预处理出行相邻情况、非法情况，打标记，然后再通过上一行限制推算该行方案数。表示第行状态为（预处理合法情况数组）的方案数，最终答案是（数组大小）。

反思

  1. 状压大多需要预处理。
  2. 保持警惕，玄学是在完全的查错无果后的解释。

代码

  1. //  La Pluie Froid
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. using namespace std;
  7. const int N=14;
  8. int lune[N],dp[N][1<<N],pluie[1<<N],n,m;
  9. int main(){
  10.     scanf("%d %d",&n,&m);
  11.     for(int i=1;i<=n;i++){
  12.         for(int j=1;j<=m;j++){
  13.             int x;
  14.             scanf("%d",&x);
  15.             lune[i]|=((!x)<<(j-1)); // 预处理非法放置 
  16.         }
  17.     }
  18.     int t=0;
  19.     for(int i=0;i<(1<<m);i++){
  20.         if(!(i&(i<<1))) pluie[++t]=i; // 如果行相邻，非法 
  21.     }
  22.     for(int i=1;i<=t;i++){
  23.         dp[1][i]=!(lune[1]&pluie[i]); // 如果第一行地形与第一行状态冲突，非法 
  24.     }
  25.     for(int i=2;i<=n;i++){ // 枚举行 
  26.         for(int j=1;j<=t;j++){ // 枚举本行状态 
  27.             if(lune[i]&pluie[j]) continue; // 如果本行地形与本行状态冲突，非法 
  28.             for(int k=1;k<=t;k++){ // 枚举上一行状态 
  29.                 if(lune[i-1]&pluie[k]) continue; // 如果上行地形与上行状态冲突，非法 
  30.                 if(pluie[j]&pluie[k]) continue; // 如果本行状态与上行状态冲突，非法 
  31.                 dp[i][j]+=dp[i-1][k];
  32.             }
  33.         }
  34.     }
  35.     int ans=0;
  36.     for(int i=1;i<=t;i++){
  37.         ans=(ans+dp[n][i])%100000000;
  38.     }
  39.     printf("%d",ans);
  40.     return 0;
  41. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注