首页 > 代码库 > UESTC 885 方老师买表

UESTC 885 方老师买表

2024-07-06 18:15:12   217人阅读

显然是一个状压DP。

将方格的摆放分成两种：

1.水平摆放：此时所占的两个格子都记为1。

2.竖直摆放：此时底下那个格子记为1，上面那个记为0。

这样的话，每行都会有一个状态表示。

定义：dp[i][s]表示考虑已经填到第i行，这一行状态为s的方法数

转移：dp[i][s] = dp[i][s]+dp[i-1][s‘]  (s‘为上一行的状态，当第i行和第i-1行能够满足条件时，进行转移)

先预处理出所有满足条件的第一行，然后从第二行开始转移。

最后答案为dp[n][(1<<m)-1].

当n<m时交换n和m可减小1<<m，即减少状态数。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
#define ll long long
using namespace std;
#define N 2100

ll dp[13][N];
int n,m;

int FirstLine(int state)
{
    int i=0;
    while(i<m)
    {
        if(state & (1<<i))   //第i列为1,第i+1列也存在且必须为1
        {
            if(i < m-1)
            {
                if(state & (1<<(i+1)))   //第i+1列为1
                    i += 2;
                else
                    return 0;
            }
            else
                return 0;
        }
        else
            i++;
    }
    return 1;
}

int Can(int ka,int kb)  //ka:这一行，kb:上一行
{
    int i = 0;
    while(i<m)
    {
        if(ka & (1<<i))  //这一行i列为1
        {
            if(kb & (1<<i))  //如果上一行i列为1，则为两个水平块
            {
                if(i < m-1 && (ka & (1<<(i+1))) && (kb & (1<<(i+1))))
                    i += 2;
                else
                    return 0;
            }
            else    //上一行为0,竖着放的
                i++;
        }
        else   //这一行i列为0,上一行i列必须填充
        {
            if(kb & (1<<i))
                i++;
            else
                return 0;
        }
    }
    return 1;
}

int main()
{
    int i,j,sa;
    int state1,state2;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if((n*m)%2)
        {
            puts("0");
            continue;
        }
        memset(dp,0,sizeof(dp));
        if(n < m)
            swap(n,m);
        int MAX = (1<<m)-1;
        for(sa=0;sa<=MAX;sa++)
        {
            if(FirstLine(sa))   //此状态可以作为第一行的状态
                dp[0][sa] = 1;
        }
        for(i=1;i<n;i++) //行递增
        {
            for(state1=0;state1<=MAX;state1++)
            {
                for(state2=0;state2<=MAX;state2++)
                {
                    if(Can(state1,state2))
                        dp[i][state1] += dp[i-1][state2];
                }
            }
        }
        printf("%lld\n",dp[n-1][MAX]);
    }
    return 0;
}
View Code

 


联系
我们