POJ：2411-Mondriaan's Dream（矩形拼接方案）

解题心得：

可以说是很经典的一个状压dp了，写dfs遍历肯定是要超时的，这个题的状态转移方程对新手来说有点吃力。
状态转移用的是上凸法，就是如果一行中（除了最后一行）有一个是空位，那么必定是下面一行竖着摆放的矩形，这样才符合条件。这样就把两行中的状态联系起来了，枚举每两行的状态来进行检验，还可以进行状态的累加。
这个题还有一些小技巧，
- 如果列数大于行数可以将列和行互换，因为在计算行和列的复杂度是完全不同的，列是o(2^n)，行是o(n)。，
- 另一个就是因为行列数量级很小，测试样例可能很多，可以把每次的答案记录下来，这样在有答案的时候可以直接输出。

#include<stdio.h>

#include<cstring>

#include<iostream>

using namespace std;

const int maxn = (1<<11)+10;

long long dp[15][maxn],ans[15][15];

int n,m,Max;

bool init(int x)

{

    int i=0;

    while(i<m)

    {

        if(x&(1<<i))

        {

            if(i == m-1)//不能超出边界

                return false;

            if(x&(1<<(i+1)))//一个横放的矩形

                i += 2;

            else

                return false;

        }

        else

            i++;

    }

    return true;

}

bool ok(int x,int y)

{

    int i = 0;

    while(i<m)

    {

        if(x&(1<<i))//两个都是横放的

        {

            if(y&(1<<i))

            {

                if(i == m-1 || !(x&(1<<(i+1))) || !(y&(1<<(i+1))))

                    return false;

                else

                    i+=2;

            }

            else

                i++;

        }

        else//当前行有放置的矩形,上一行是空

        {

            if(y&(1<<i))

                i++;

            else

                return false;

        }

    }

    return true;

}

void solve()

{

    Max = (1<<m) -1;

    memset(dp,0,sizeof(dp));

    for(int i=0;i<=Max;i++)//特殊的第一行初始化

    {

        if(init(i))

            dp[0][i] = 1;

    }

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

        for(int s=0;s<=Max;s++)//枚举每两行符合条件的放置方式

            for(int ss=0;ss<=Max;ss++)

            {

                if(ok(s,ss))

                    dp[i][s] += dp[i-1][ss];

            }

    printf("%lld\n",ans[n][m] = ans[m][n] = dp[n-1][Max]);

}

int main()

{

    memset(ans,0,sizeof(ans));

    while(cin>>n>>m)

    {

        if(m > n)//如果行小于列，直接交换行和列

            swap(n,m);

        if(n+m == 0)

            break;

        if(ans[n][m] || ans[m][n])//记录已经出现过的答案

        {

            printf("%lld\n",ans[n][m]);

            continue;

        }

        if((n*m)%2 == 1)//如果行列都是奇数那么没有符合条件的方案

        {

            printf("0\n");

            continue;

        }

        solve();

    }

}

巴特西

POJ：2411-Mondriaan's Dream（矩形拼接方案）

最新文章

热门文章