題目：BZOJ1088、洛谷P2327、Vijos P1193、codevs2452。

題目大意：經典的掃雷游戲（不要告訴我你連掃雷都沒玩過），右邊一排沒有雷，給出右邊一排的信息，求左邊一排有多少種滿足條件的擺雷方案。

解題思路：我們發現，只要知道左邊一排第一格有沒有雷，就可以根據右邊一排推出下面所有的雷。推出來以后我們只要判斷是否滿足右邊一排最后一格的條件即可。簡單的遞推。

C++ Code：

#include<cstdio> #include<cstring> using namespace std; int a[10002],n,ans; int f[10002]; void pd(){for(int i=2;i<=n;++i){int cnt=f[i-1]+f[i-2];if(cnt>a[i-1]||a[i-1]-cnt>1)return;f[i]=a[i-1]-cnt;}if(f[n]+f[n-1]!=a[n])return;ans++; } int main(){scanf("%d",&n);ans=0;for(int i=1;i<=n;++i)scanf("%d",&a[i]);f[0]=0;for(f[1]=0;f[1]<2;++f[1])//枚舉第一格有沒有雷 pd();printf("%d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/Mrsrz/p/7380231.html

總結

以上是生活随笔為你收集整理的[SCOI2005]扫雷的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。