【Luogu】P1879玉米田（状压DP）

题目链接

数据范围这么小，难度又这么大，一般就是状态压缩DP了。

对输入进行处理，二进制表示每一行的草地状况。如111表示这一行草地肥沃，压缩成7.

所以f[i][j]表示第i行状态为j时的方案数

状态j指的是一个二进制集合，有牛在吃草的位置是1，不再吃草的位置是0

f[i][j]=Sum(f[i-1][k])

限制：(1) j必须是草地状况的子集。很好理解，如果有牛在贫瘠草地上吃草……会被投诉到动物保护协会的

(2) j 的相邻两个位置不能都是1。代码表示为!(j&(j<<1)

(3) k 的上述两个限制。

(4) k和j没有交集。这样可以保证没有相邻两个位置是1。

代码如下

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<iostream>

#define mod 100000000

#define Max ((1<<m)-1)

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int f[][]={};

int s[];

int ans;

int main(){

    int n=read(),m=read();

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

        for(int j=;j<=m;++j){

            int x=read();

            s[i]=(s[i]<<)+x;

        }

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

        for(int j=;j<=Max;++j){

            if(((j|s[i])!=s[i])||(j&(j<<)))    continue;

            for(int k=;k<=Max;++k){

                if(((k|s[i-])!=s[i-])||(k&(k<<))||(k&j))    continue;

                f[i][j]=(f[i][j]+f[i-][k])%mod;

            }

        }

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

        ans=(ans+f[n][i])%mod;

    printf("%d",ans);

    return ;

}

巴特西

【Luogu】P1879玉米田（状压DP）

最新文章

热门文章