Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 2821
Solved 1670

Description

相信大家都玩过扫雷的游戏. 那是在一个 n*m 的矩阵里面有一些雷, 要你根据一些信息找出雷来. 万圣节到了, “余” 人国流行起了一种简单的扫雷游戏, 这个游戏规则和扫雷一样, 如果某个格子没有雷, 那么它里面的数字表示和它 8 连通的格子里面雷的数目. 现在棋盘是 n×2 的, 第一列里面某些格子是雷, 而第二列没有雷, 如下图: 由于第一列的雷可能有多种方案满足第二列的数的限制, 你的任务即根据第二列的信息确定第一列雷有多少种摆放方案.

Input

第一行为 N, 第二行有 N 个数, 依次为第二列的格子中的数. (1<=N <=10000)

Output

一个数, 即第一列中雷的摆放方案数.

Sample Input

2
1 1

Sample Output

2

HINT

Source

很简单的一个 DP, 因为并不需要考虑到回溯问题, 所以 DP 可以秒解.

注意不要写错~ 因为有特判......


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 10010;

int n, res;
int arr[maxn];
int dp[maxn];

bool judge_possibility(void)
{
    for (int i = 3; i <= n + 1; i++) {
        dp[i] = arr[i - 1] - dp[i - 1] - dp[i - 2];
        if (dp[i] < 0)
            return false;
    }
    if (arr[n] != dp[n - 1] + dp[n])
        return false; // Even at the end, we still have to check intactness
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    // Take on every possibility of the first grid and that's it
    // Meaning the answer would not exceed the range[0, 2]
    if (arr[1] == 0) {
        memset(dp, 0, sizeof(dp));
        dp[1] = 0, dp[2] = 0;
        res += judge_possibility();
    } else if (arr[1] == 1) {
        memset(dp, 0, sizeof(dp));
        dp[1] = 1, dp[2] = 0;
        res += judge_possibility();
        memset(dp, 0, sizeof(dp));
        dp[1] = 0, dp[2] = 1;
        res += judge_possibility();
    } else if (arr[1] == 2) {
        memset(dp, 0, sizeof(dp));
        dp[1] = 1, dp[2] = 1;
        res += judge_possibility();
    } else {
        res = 0;
    }
    printf("%d\n", res);
    return 0;
}
from pydatagen import *
n = randrange(5000, 10000)
printf('%d\n' % n)
a = [0] + randlist(n, [0, 1]) + [0]
for i in range(1, n + 1):
    printf('%d ' % (a[i - 1] + a[i] + a[i + 1]))