今天做了几道BZOJ的题，发现统观题目时还是很多很多都不会的，不过还是有几道时可以作的，以后要慢慢加强，争取多做题

BZOJ 1088 扫雷

其实本人平常不大玩扫雷的，就算玩也不是很好，不过看n*2的扫雷，也是微醺啊QAQ

1088: [SCOI2005]扫雷Mine

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 2299 Solved: 1345

[Submit][Status][Discuss]

Description

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

Input

第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

Output

一个数，即第一列中雷的摆放方案数。

Sample Input

2

1 1

Sample Output

2

这道题可以看出，因为知道第二列每个点附近有几个雷，有知道附近指的是八联通，又因为是n*2的雷区。。所以不难想到，每个第二列的点，炸弹数分布在三个格中（收尾除外，为两个），所以由第二列第一个点附近的雷数，可以得到第一列第一二格是否有雷，所以往下找就能找到，最后只需要判断是否合法就好

其转移可表示为

boom[i]=num[i-1]-(boom[i-1]+boom[i-2]);

（num为第二列的点的值，boom是第一列是否有雷0无雷1有雷）

下面是代码（写到一半发现其实写个过程就简短多了，然而。。。）/(ㄒoㄒ)/~~

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n;

int num[10010]={0};//存储第二列的每个格里的数，及附近炸弹数

int boom[10010]={0};//第一列是否有炸弹（0为无炸弹，1为炸弹）

int ans=1;

int main()

{

    scanf("%d",&n);

    memset(boom,0,sizeof(boom));

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

        scanf("%d",&num[i]);

   if (num[1]!=1)//因为第一个点可以控制两个点的炸弹数，如果的得知第一个点周围没炸弹或有两个炸弹，那么前两个点都有炸弹或都没有炸弹

   {

        ans=1;

        if (num[1]==0)

        boom[1]=boom[2]=0;

    if (num[1]==2)

        boom[1]=boom[2]=1;

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

            boom[i]=num[i-1]-(boom[i-1]+boom[i-2]);

    if (boom[n+1]!=0)//判断是否可行

        ans--;//因为ans初值为1，所以如果不可行减1即可

   }

  if (num[1]==1)//如果第一个点附近有一个炸弹，则有两种情况（1） 第一个点有炸弹，第二个点没有 （2）第一个点没有，第二个点有

        {

            ans=2;

            boom[1]=1;

            boom[2]=0;

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

                    boom[i]=num[i-1]-(boom[i-1]+boom[i-2]);

            if (boom[n+1]!=0)

                ans--;//第一种情况

            boom[1]=0;

            boom[2]=1;

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

                    boom[i]=num[i-1]-(boom[i-1]+boom[i-2]);

            if (boom[n+1]!=0)

                ans--;//第二种情况

        }

   printf("%d",ans);

}