luogu2327 扫雷

S1

这道题的算法没有任何的隐藏，妥妥的DP。
第一种思路，用f[i][0/1]来表示第i个放不放地雷。
先做预处理，第二列是3的绝对都选，首或者尾是2就绝对都选，再看第二列是2的，如果周围已经有两个必须放地雷就绝对不选，在看第二列是1的，如果周围已经放上地雷了就绝对不选，然后开始DP。
但是这样的话后效性实在太强，无法操作。

S2

考虑一下加维来消除后效性，f[i][0/1][0/1]，加一维来表示前一个的前一个选不选。
但是这样出来的代码只有二十分，不能考虑到每一格后面的格子选什么对总体的影响。

S3

看题解
其实之前手糊数据的时候就应该想到的，整个队列长成什么样其实完全取决于第一个放还是不放，而答案也只可能有0，1，2三种情况。
那么只需要枚举就可以，连DP也不用……
当然运用这种思路进行DP更容易一些，但我万万没想到的是，这道题还真的跟扫雷有关系。
对于某一点i，i-1的数字决定了i-2,i-1,i这三个点里面有几个雷，所以直接可以推出方程b[i]=a[i-1]-b[i-1]-b[i-2]，如果不等于1或0，那么就说明这样行不通。最后再特判一下最后一个格子就好了，其实并不难，就是思维僵化，认为f[i]只能通过a[i]来推，而并没有结合题目实际进行状态转移。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define big 1e9
using namespace std;
int n,a[10001],b[10001],ans;
int main()
{
    scanf("%d",&n);
    for (rint i=1;i<=n;i++) scanf("%d",&a[i]);
    for (rint i=0;i<=1;i++)
    {
        memset(b,0,sizeof(b));
        b[1]=i;b[2]=a[1]-b[1];
        bool flag=1;
        for (rint j=3;j<=n;j++)
        {
            b[j]=a[j-1]-b[j-1]-b[j-2];
            if (b[j]!=1 && b[j]!=0)
            {
                flag=0;
                break;
            }
        }
        if (b[n]!=a[n]-b[n-1]) flag=0;
        if (!flag) continue;
        ans++;
    }
    printf("%d",ans);
}

总结：

1. 如果DP方案后效性太强，除非万不得已，干脆不要去打。
2. DP的形式不是死的，要让思维活起来，以做出这道题为最终目的。