Rockdu's Blog

2
1  1

2​​

一道很小型的状压，我们用一个二位二进制记录到当前行的时候，当前行的下一格和当前行对应的格子是否为地雷。这样我们就可以根据信息递推状态转移方程，具体见代码：

#include<cstdio>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e4 + 5;
LL dp[maxn][5];
int num[maxn], now, n;

int main() {
    scanf("%d", &n);
    For(i, 1, n) scanf("%d", &num[i]);
    dp[0][0] = dp[0][1] = 1;
    For(i, 0, n - 1) {
        For(k, 0, 3) {
            now = dp[i][k];
            int G = (k << 1 | 1) % 4, U = (k << 1) % 4;
            if(num[i + 1] == 0 && !(k & 1) && !(k & 2)) 
                dp[i + 1][U] += now;
            if(num[i + 1] == 1) {
                if(k & 2 && !(k & 1)) dp[i + 1][U] += now;
                if(!(k & 2) && k & 1) dp[i + 1][U] += now;
                if(!(k & 2) && !(k & 1)) dp[i + 1][G] += now;
            }
            if(num[i + 1] == 2) {
                if(k & 2 && !(k & 1)) dp[i + 1][G] += now;
                if(k & 1 && !(k & 2)) dp[i + 1][G] += now;
                if((k & 3) == 3) dp[i + 1][U] += now;
            }
            if(num[i + 1] == 3) {
                if((k & 3) == 3) dp[i + 1][G] += now;
            }
        }
        //if(i == 0) dp[1][2] = dp[1][3] = 0;
    }
    printf("%lld", dp[n][0] + dp[n][2]);
    return 0;
}