LUOGU P1879 [USACO06NOV]Corn Fields G

快被做烂的方案数状压DP

设状态为一个正整数 (S) ,其在二进制的第 (i) 位若为 (1) 则表示在这一块有草地

例如 (S = (0010)_2) 表示在第 (2) 列有草地,而其他列没有草地

那么 设 (f(i,S)) 表示 在第 (i) 行 状态为 (S) 时的最优解

状态转移方程即 (f(i,S) = sum f(i-1,p)) 其中 (p) 合法

因为这道题限定了状态，即限定了那些地方肥沃

为了解决这个问题 我引入了 (mp) 数组

(mp(i)) 表示第 (i) 行 (...)

for(int i=1;i<=m;++i)
    for(int j=1;j<=n;++j) {
        scanf("%d",&x);
        mp[i] |= (x^1)<<(j-1);
    } // 读入

rt，若允许的每行的最大状态为 ((1110)_2) 则 (mp(i) = (0001)_2)

那么状态转移方程的条件就可以列出来了

即 每个状态 (S) 满足 !(j&(j<<1)||j&mp[i])

每个状态 (p) 满足 !(p&(p<<1)||p&mp[i-1])

然后就能快乐的打代码了

// P1879 [USACO06NOV]玉米田Corn Fields
// 设计状态
// f[i][j] 表示 在第i行 状态为j时的最优解
// f[i][j] = sigma(f[i-1][p])
#include<bits/stdc++.h>
using namespace std;
const int p = (int)1e8;
long long f[13][1<<12];
int mp[13],m,n,x;
int main() {
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j) {
            scanf("%d",&x);
            mp[i] |= (x^1)<<(j-1);
        }
    for(int i=0;i<(1<<n);++i) if(!(i&mp[1]||i&(i<<1))) f[1][i] = 1;
    for(int i=2;i<=m;++i)
        for(int j=0;j<(1<<n);++j) {
            if(j&(j<<1)||j&mp[i]) continue ;
            for(int k=0;k<(1<<n);++k) {
                if(j&k||k&mp[i-1]) continue ;
                f[i][j] = (f[i][j] + f[i-1][k]) % p;
            }
        }
    long long ans = 0;
    for(int i=0;i<(1<<n);++i) ans = (ans + f[m][i]) % p;
    printf("%lld",ans);
    return 0;
}