题解 P5074 【Eat the Trees】

· · 题解

插头 DP 简单题，不需要括号序列。

滚动数组，每次从 f 转移到 g。

每次考虑当前方格下方和右方的插头，看从左方和上方的什么状态转移过来：
00 从 11 转移，01 从 01 和 10 转移，10 从 01 和 10 转移，11 从 00 转移。

写成位运算的形式就是 g[b]=f[b^3<<j]+((b>>j&1)^(b>>j+1&1)?f[b]:0)，b 是状态。

要注意行末/初的时候要对状态进行移位的特殊处理。开 long long。

复杂度 \Theta(nm2^{m+1})。

#include<cstdio>
#define F(i,n) for(int i=0;i<n;++i)
int T,n,m,s,c[12][12];
long long f[1<<13],g[1<<13];
int main(){
    for(scanf("%d",&T);T--;){
        scanf("%d%d",&n,&m);s=1<<m+1;
        F(i,n)F(j,m)scanf("%d",&c[i][j]);
        F(i,s)g[i]=0;g[0]=1;
        F(i,n)F(j,m){
            F(b,s)f[b]=j?g[b]:b&1?0:g[b>>1];
            if(!c[i][j])F(b,s)g[b]=b>>j&3?0:f[b];
            else F(b,s)g[b]=f[b^3<<j]+((b>>j&1)^(b>>j+1&1)?f[b]:0);
        }printf("%lld\n",g[0]);
    }
    return 0;
}