Bzoj 1088: [SCOI2005]扫雷Mine

怒写一发,算不上DP的游戏题

知道了前$i-1$项,第$i$项会被第二列的第$i-1$得知

设$f[i]$为第一列的第$i$行位置是否有雷,有雷的话,$f[i] = 1$,无雷$f[i] = 0$

$a[i]$就是题目读入的东西.

那么转移方程就是$f[i] = a[i - 1] - f[i - 1] - f[i - 2]$

不满足限制的时候就是$f[i] < 0$ 或者$ f[i] > 1$

第一个位置讨论一下即可.进行上面的递推.

#include <iostream>

#include <cstdio>

const int maxN = 10000 + 7;

int f[maxN],ans,a[maxN];

inline int read() {

    int 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 n;

void work() {

    for(int i = 2;i <= n;++ i) {

        f[i] = a[i - 1] - f[i - 1] - f[i - 2];

        if(f[i] < 0 || f[i] > 1) return ;

    }

    if(a[n] != f[n] + f[n - 1])return ;

    ans ++;

    return ;

}

int main() {

    n = read();

    for(int i = 1;i <= n;++ i)

        a[i] = read();

    for(int i = 0;i < 2;++ i)

        f[1] = i,work();

    printf("%d\n", ans);

    return 0;

}

巴特西

Bzoj 1088: [SCOI2005]扫雷Mine (DP)

Bzoj 1088: [SCOI2005]扫雷Mine

最新文章

热门文章