xindoo is
always here

poj 3254 Corn Fields (状态压缩dp)


题目链接

题意:Farmer John 放牧cow,有些草地上的草是不能吃的,用0表示,然后规定两头牛不能相邻放牧。问你有多少种放牧方法。

      状态压缩dp其实就是用二进制来表示所有的状态,比如这题, 我们在某一行可以这样取0 1 0 1 1 0 1,用1代表取了,0代表没取,因为这点,它的数据量也限制在20以内,所有看到这样数据量的题目可以先考虑一下状态压缩dp。对于有多行的数据,所有状态的总数必然很庞大,而且不用特殊的方法想要存储这些状态是不太现实的。既然每个点只有这两种情况,我们可以用二进制的一位来表示,0 1 0 1 1 0 1就可以表示为二进制0101101也就是十进制的45,如果我们想要枚举6个点的所有状态,我们只需要从0到2^6取其二进制就可以了,并不会重复或是多余。

      然后关于这题,题目要求不相邻,也就是说每个状态中不能有两个1相邻,代码中我用了checkself()函数判断。还有,有些地方是非法的,我在输入的时候将非法的状态保存了,一行只占一个整数,只需要判断某状态中只要有个一位和非法状态总的一位都为1,这个状态必然非法,这里我用了check()函数。

      我们检测完了状态的合法性,接下来就是状态转移的问题了。对于当前行的合法状态,到这个状态的方法数目一定是前一行与它不冲突(也就是没有行之间相邻的点)的方法数之和(记得mod)。这样求出到最后一行所有状态的方法数,求其和,然后取余,这就是我们要的结果。



#include <stdio.h>
#include <string.h>
#define MOD  100000000
#define maxn 13

int dp[maxn][1<<maxn];        //每个状态可以放牧方法的总数
int n, m;
int sta[maxn];                //能不能放牧的状态

bool check(int x, int y)      //检查同列有没有相邻的或者x的状态是否可以存在
{
    if (x&y)
        return false;
    return true;
}

bool checkself(int x)         //检查同行有没有相邻的
{
    if (x&(x<<1))
        return false;
    return true;
}

int getresult()
{
    int num = 1<<m;
    for (int i = 0; i < num; i++)
    {
        if (check(i, sta[1]) && checkself(i))
            dp[1][i] = 1;
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j < num; j++)
        {
            if (!check(j, sta[i]))                    //sta[i]表示i行不能存在的状态
                continue;
            for (int k = 0; k < num; k++)
            {
                if (check(k, j) && checkself(j) && checkself(k))
                    dp[i][j] += (dp[i-1][k]%MOD);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < num; i++)
    {
        ans += (dp[n][i]%MOD);
    }
    return ans%MOD;
}

int main()
{
    int t;
    while (scanf("%d %d", &n, &m) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                scanf("%d", &t);
                if (!t)
                {
                    sta[i] += (1<<(m-j));            //这里对不能出现的状态做标记
                }
            }
        }
        printf("%d\n", getresult());
    }
    return 0;
}


打赏
未经允许不得转载:XINDOO » poj 3254 Corn Fields (状态压缩dp)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏