bzoj1088 P2327 [SCOI2005]扫雷

P2327 [SCOI2005]扫雷

emmmmm…..这题真可以用状压写

因为每个数字只对3个格子有影响，相当于只有2^3=8种状态，所以可以用状压瞎搞

我们用8个数字代表二进制下的8种状态

0 000　;　1 001　;　2 010　;　3 011　;

4 100　;　5 101　;　6 110　;　7 111　;

0/1表示无/有雷

设 f[ i ][ j ]表示在第 i-2 ~ i 个格子的状态为 j 的方案数

状态转移时（设当前状态为 i）相当于 f[ i+1 ][ j ]=f[ i ][ j>>1 ]+f[ i ][ j>>1|1 ]

但是我懒得写判断所以直接手算可行转移了（逃

注意不能省略 三个格都为0的情况

#include<cstdio>
using namespace std;
int n,f[][];
int main(){
    scanf("%d",&n); int opt;
    scanf("%d",&opt);
    if(opt==) f[][]=f[][]=;
    else if(opt==) f[][]=;
    else if(opt==) f[][]=;
    for(int i=;i<=n;++i){//把数字转二进制自己观察吧qwq
        scanf("%d",&opt);
        if(opt==){
            f[i+][]=f[i][]+f[i][];
            f[i+][]=f[i][]+f[i][];
            f[i+][]=f[i][]+f[i][];
        }else if(opt==){
            f[i+][]=f[i][]+f[i][];
            f[i+][]=f[i][]+f[i][];
            f[i+][]=f[i][]+f[i][];
        }else if(opt==) f[i+][]=f[i][]+f[i][];
        else f[i+][]=f[i][]+f[i][];
    }
    printf("%d",f[n+][]+f[n+][]+f[n+][]+f[n+][]); //注意第 n+1 个格子必须为0
    return ;
}