[每日一题] [NC20241] 扫雷MINE

题目大意：Nx2列的扫雷，第二列没有雷，并且第二列每个数代表周围八个里面有多少雷。给定第二列的数，问有几种排法。

https://ac.nowcoder.com/acm/problem/20241

很经典的状态压缩DP。可以认为有一个01数组，然后知道每连续三位的总和。问有多少种方法。

====

仔细一想，其实如果知道第一第二个是多少就可以依次推出所有的雷，所以直接就是4*N次。答案最大也就是4（估计还达不到）。

int N;
#define MAXN 10005
int cnt[MAXN];
ll dp[2][2][2];
ll doit() {
  // dp[i][curr][nxt] stores the count.
  dp[0][0][0] = (cnt[0] == 0);
  dp[0][0][1] = dp[0][1][0] = (cnt[0] == 1);
  dp[0][1][1] = (cnt[0] == 2);
  FOR(i,1,N-1){
    REP(curr,2){
      REP(nxt,2){
        dp[i%2][curr][nxt]=0;
        REP(prev,2){
          if(prev+nxt+curr==cnt[i]){
            dp[i%2][curr][nxt]+=dp[1-i%2][prev][curr];
          }
        }
      }
    }
  }
  ll ans = dp[1-N%2][0][0]+dp[1-N%2][1][0];
  return ans;
}
int main(int argc, char* argv[]) {
  while (scanf("%d",&N)==1){
    read(cnt, N);
    print(doit());
  }
  return 0;
}