题目描述
相信大家都玩过扫雷的游戏。那是在一个n×m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图：
由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。
输入输出格式
输入格式：
第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）
输出格式：
一个数，即第一列中雷的摆放方案数。
【题解】
一看这道题，就知道DP一定能做，但有没有更优解法呢？
当然有！（没有我还说啥）就是你，递推，出来吧！
首先，我们先定义b[i]表示当前三个位置a[i]+a[i+1]+a[i-1]的总和（就是它上面三个数），所以在推出前两个数量的情况下可以得到第三个的数量。
我们枚举第一格雷的情况和第二格雷的情况，就能推出第三格雷的情况，就能推出以后所有的情况。
那怎么判是否可行呢？如果最后的格子之后的格子仍有雷剩余，表示分配和实际不符，若刚好分配完雷，则方案数+1。
想到这里，这题就结束了，是不是很神奇（水）呢？
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define num ch-'0' void print(int x) { if(x<0){putchar('-');x=-x;} if(x>9) print(x/10); putchar(x%10+'0'); } void get(int &res) { char ch;bool flag=0; while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); for(res=num;isdigit(ch=getchar());res=res*10+num); (flag)&&(res=-res); } int n,top,ans; int b[100010]; int a[100010]; inline void work()//如题解 { for(int i=2;i<=n+1;i++) { b[i]=a[i-1]-b[i-2]-b[i-1]; if(b[i]>1) return; } if(b[n+1]==0)ans++; } int main() { get(n); for(int i=1;i<=n;i++) get(a[i]); if(a[1]>2)//第一格不可能是3 { printf("0"); return 0; } for(int i=0;i<=2;i++)//枚举第一个格中雷的不同情况 { memset(b,0,sizeof(b));//初始化 b[1]=i; work(); } print(ans); }