P2327 [SCOI2005] 扫雷

## 曾经的lofterOI一血。 虽然这是在模拟复习课上讲的题，但我的第一反应果然还是DFS233333 最初的暴力想法是，在每个点上搜索，枚举相邻点是否有雷，O(2^n)，这样估摸着能得30分。 然后某位大佬光速回答：用DP然后把我们其他人都怒虐了一遍，不得不叹服dalao。 可以看出，当我们知道f[i]，f[i-1]，a[i]的时候，f[i+1]是直接可以算出来的。 f[i]代表1行i列的雷数量，枚举f[1]=0或1的情况，f[i+1]=a[i]-f[i]-f[i-1]，当f[i+1]大于1或小于0时直接Break，最后判断f[n+1]是否有雷，如果无雷代表合法。 所以最后的答案只有012三种。 【有人专门测试过输出012的得分 代码量十分小，貌似洛谷有相似题解。 ```cpp #include<cstdio> #define f(i,a,b) for(i=a;i<=b;++i) int flag,n,a[10010],f[10010]; int main() { // freopen("minesweeper.in","r",stdin); // freopen("minesweeper.out","w",stdout); int i,j; scanf("%d",&n); f(i,1,n)scanf("%d",&a[i]); f[1]=0; f(i,1,n) {f[i+1]=a[i]-f[i]-f[i-1];if(f[i+1]>1||f[i+1]<0)break;} if(i==n+1&&f[i]==0)++flag; f[1]=1; f(i,1,n) {f[i+1]=a[i]-f[i]-f[i-1];if(f[i+1]>1||f[i+1]<0)break;} if(i==n+1&&f[i]==0)++flag; printf("%d\n",flag); } ``` ## 曾经写下的“876\*292的白色你满意了吧”