problem

一个的扫雷棋盘,第二列没有雷,每个位置写着附近雷的个数。然后在第一个棋盘上摆放一些雷,使其满足第二列的要求,问方案数。

solution

当第一列的第一个位置确定了之后,那么后面的位置也确定了。所以就枚举一下第一个位置是0还是1,然后看一下是不是能构造出可行方案,可以的话就会让答案加1。

考虑如何构造方案,当我们对于一个位置i进行决策的时候,这个位置就是第2列的第个位置满足条件的最后希望了,所以我们直接让第个位置按照的要求放。然后将相应的减去第i个位置的值即可。

code

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<ctime>
#include<set>
using namespace std;
typedef long long ll;
const int N = 10010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int a[N],b[N],c[N],n;
int solve() {
    for(int i = 1;i <= n;++i) c[i] = a[i];
    c[1] -= b[1];c[2] -= b[1];
    for(int i = 2;i <= n;++i) {
        b[i] = min(1,max(0,c[i - 1]));
        c[i - 1] -= b[i];
        c[i] -= b[i];
        c[i + 1] -= b[i];
    }
    for(int i = 1;i <= n;++i) {
        if(c[i] != 0) return 0;
    }
    return 1;
}
int main() {
    n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    int ans = 0;
    if(a[1] == 1 || a[1] == 2) {
        b[1] = 1;ans += solve();
    }
    if(a[1] == 1 || a[1] == 0) {
        b[1] = 0;ans += solve();
    }
    cout<<ans<<endl;

    return 0;
}