【暴力】【推导】bzoj1088 [SCOI2005]扫雷Mine

考虑右侧的一个格子是否放雷，只可能对其左侧的三个格子造成影响。

也就是说，若左侧一个格子旁的两个格子已经放了雷，对第三个格子也就唯一确定了。

因此只枚举前两个格子是否放雷，剩下的暴力判断是否合法即可。

但是再想想，左侧第一个格子只受右侧前两个格子的影响。所以只枚举右侧第一个格子是否放雷，剩下的判断是否合法即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int n,a[10001],t[10001],ans;
 5 bool b[10001];
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
10     memcpy(t,a,sizeof(a));
11     b[1]=1; a[1]--; a[2]--;
12     for(int i=2;i<=n;i++)
13       if(a[i-1])
14         {
15           b[i]=1; a[i-1]--; a[i]--; a[i+1]--;
16           if(a[i-1]!=0) goto FAIL;
17         }
18     if(a[n]!=0||a[n-1]!=0) goto FAIL;
19     ans++;
20     FAIL: memset(b,0,sizeof(b));
21     memcpy(a,t,sizeof(a));
22     for(int i=2;i<=n;i++)
23       if(a[i-1])
24         {
25           b[i]=1; a[i-1]--; a[i]--; a[i+1]--;
26           if(a[i-1]!=0) goto FAIL2;
27         }
28     if(a[n]!=0||a[n-1]!=0) goto FAIL2;
29     ans++;
30     FAIL2: printf("%d
",ans);
31     return 0;
32 }