题解 P1879 【[USACO06NOV]玉米田Corn Fields】

zzy_123 · 2019-02-17 11:35:57 · 题解

这个题目看了其他大佬的题解都没有看懂，通过P1896互不侵扰学会的状压， 于是运用相同的方法来写这个题目，和那个题目的转移方程基本相同，这一行的某种方案的方案数为上一行的所有可行的的方案数相加,最后把最后一行的所有方案的方案数相加。

#include<bits/stdc++.h>
using namespace std;
long long int n,m,ans=0;
long long int f[20][20],j[25][2500],k[20],l[20][2000];
//f储存田地的好坏 j来储存方案 k表示方案数 l为状态转移 
void chuli()
{
    int a,b,c,d,e;//利用2进制储存状态，1表示种草，0表示不种，如9表示1001 
    for(a=1; a<=n; a++)
    {
        for(b=0; b<pow(2,m); b++)//考虑所以情况，不用忘记全部荒废也是一种 
        {
            if(b&(b<<1))continue;//不能有草地相邻，利用位运算快速算出 
            for(c=0; c<m; c++)
            {
                if(((1<<c)&b)&&f[a][m-c]==0)break;//如果是在0的田地上种草则返回 
            }
            if(c==m)j[a][++k[a]]=b;//储存状态 
        }
    }
}
void work()
{
    int a,b,c,d,e;
    for(a=1;a<=k[1];a++)l[1][a]=1;//n=1的情况直接考虑      
    for(a=2; a<=n; a++)
    {
        for(b=1; b<=k[a]; b++)//枚举所有方案 
        {
            for(c=1; c<=k[a-1]; c++)//枚举上一行的方案 
            {
                if(j[a][b]&j[a-1][c])continue;//利用位运算快速求出是否相邻 
                l[a][b]=l[a-1][c]+l[a][b];
                l[a][b]%=1000000000;
            }
        }
    }
    for(a=1; a<=k[n]; a++)
    {
        ans+=l[n][a];
        ans%=1000000000;
    }
    cout<<ans<<" ";
}
int main()
{
    int a,b,c,d,e;
    cin>>n>>m;
    for(a=1; a<=n; a++)
    for(b=1; b<=m; b++)cin>>f[a][b];
    chuli();
    work();
}