https://www.luogu.org/problem/show?pid=2327

做法:

dp.dp[i][j]表示到第i位的附近三格，有几种形状为j的可能

“形状为j”是什么意思呢，注意到如果附近三格有无雷用0，1表示的话，其实就组成了二进制数字，把他们转化为十进制即为j

那么j最大是7

转移的话直接根据上一次结果和当前数字判断即可，我用了滚动数组

O(n)
[code lang="cpp"]
#include<cstdio>
#include<cstring>
#define MAXN 10010
using namespace std;
int dp[2][8];
int a[MAXN];
int n, ans = 0;
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] > 3) {
printf("0");
return 0;
}
}
if (a[n] == 3){
printf("0");
return 0;
}
if (n == 1){
if (a[1] == 1) printf("1");
else printf("0");
return 0;
}
memset(dp, 0, sizeof(dp));
if (a[1] == 0) dp[0][0] = 1;
if (a[1] == 1) dp[0][2] = 1, dp[0][1] = 1;
if (a[1] == 2) dp[0][3] = 1;
for (int i = 2; i <= n; i++){
int w = i & 1;
int v = (i - 1) & 1;
memset(dp[v], 0, sizeof(dp[v]));
if (a[i] == 0){//查看前面以0结尾的数
dp[v][0] += dp[w][4];
dp[v][0] += dp[w][0];
}
if (a[i] == 1) {
if (i != n) dp[v][1] += dp[w][0] + dp[w][4];
dp[v][4] += dp[w][2] + dp[w][6];
dp[v][2] += dp[w][1] + dp[w][5];
}
if (a[i] == 2) {
if (i != n) dp[v][5] += dp[w][2] + dp[w][6];
dp[v][3] += dp[w][1] + dp[w][5];
dp[v][6] += dp[w][3] + dp[w][7];
}
if (a[i] == 3) {
dp[v][7] += dp[w][3] + dp[w][7];
}
}

for (int i = 0; i < 8; i++){
ans += dp[(n - 1) & 1][i];
}
printf("%d", ans);
}
[/code]