M_sea

洛谷2327 [SCOI2005]扫雷
题目描述传送门算法DFS这题可以直接DFS,不过时间复杂度为O(2^n),会TLE。DP右侧的雷数已经给出了,每个...
扫描右侧二维码阅读全文
12
2017/09

洛谷2327 [SCOI2005]扫雷

题目描述

img

传送门

算法

DFS

这题可以直接DFS,不过时间复杂度为O(2^n),会TLE。

DP

右侧的雷数已经给出了,每个地方的状态只有两种,有雷或没雷。
如果第一个格子的状态已经确定下来了,那么这个序列的状态也就确定下来了。
所以答案只有3种,即0,1或2。

设$f[i] [0]$表示第一列第i个格子应有的雷数,$f[i] [1]$表示第二列的数字。
那么得到状态转移方程(实际上画个图就能想到,容易理解):

$$f[i][0]=f[i-1][1]-f[i-1][0]-f[i-2][0]$$

边界有两个:$f[1] [0]=1$和$f[1] [0]=0$。
答案就是这两个边界的成立数。

还有一个特判:$f[n] [1]$是否等于$f[n] [0]+f[n-1] [0]$。因为$f[n] [1]$在递推时没有用到,那么就有可能发生状态矛盾,所以要特判一下。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int f[10010][2];
int ans=0,n;
inline int read() //读入优化
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
bool DP(int start) //f[1][0]=start的情况是否成立
{
    f[1][0]=start; //边界值
    for (int i=2;i<=n;i++) //一路递推/DP过去
    {
        f[i][0]=f[i-1][1]-f[i-1][0]-f[i-2][0];
        if ((f[i][0]!=0)&&(f[i][0]!=1)) return false; //不是(不是雷)或(是雷)这两种状态,不成立
        if (i==n&&(f[i][0]+f[i-1][0])!=f[i][1]) return false; //说过的特判
    }
    return true; //成立,返回
}
int main()
{
    n=read();
    for (re int i=1;i<=n;i++) f[i][1]=read(); //输入
    ans+=DP(0); ans+=DP(1); //递推/DP计算答案
    printf("%d\n",ans); //输出
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 08 PM

发表评论