【题解】洛谷P1879 [USACO06NOV] Corn Fields（状压DP）

思路

把题目翻译成人话

在n*m的棋盘 每个格子不是0就是1

1表示可以种 0表示不能种 相邻的格子不能同时种 求总方案数

把每行看成一个n位的2进制数 预处理出每行的状态后 进行DP即可

PS：在处理每行的初始状态时 将其取反后更好操作

代码

#include<iostream>

#include<cstdio>

using namespace std;

#define mod 100000000

int f[][];

int n,m,ans;

struct State

{

    int st[];

    int num;

}a[];

void getstate(int i,int t)

{

    int num=;//记录此行有几种状态

    for(int j=;j<(<<n);j++)//枚举所有状态

    {

        if((j&t)||(j&(j<<))||(j&(j>>))) continue;//如果冲突就跳过

        a[i].st[++num]=j;//记录状态

        a[i].num=num;

    }

}

void dp()

{

    for(int i=;i<=a[].num;i++) f[][i]=;//初始化

    for(int i=;i<=m;i++)//枚举行

    {

        for(int j=;j<=a[i].num;j++)//枚举第i行的状态

        {

            f[i][j]=;

            for(int k=;k<=a[i-].num;k++)//枚举第i-1行的状态

            {

                if(a[i].st[j]&a[i-].st[k]) continue;//如果冲突就跳过

                f[i][j]+=f[i-][k];//累计ans

            }

        }

    }

    for(int i=;i<=a[m].num;i++)

    ans=(ans+f[m][i])%mod;//累计第m行的所有状态的ans

    printf("%d",ans);

}

int main()

{

    scanf("%d%d",&m,&n);

    for(int i=;i<=m;i++)

    {

        int t=;//处理当前行的状态

        for(int j=;j<=n;j++)

        {

            int x;

            cin>>x;//这里对输入进行取反操作

            t=(t<<)+-x;//如1010 存成0101 方便后面判断状态

        }

        getstate(i,t);//获得此行状态

    }

    dp();

}