POJ 2411 Mondriaan's Dream —

【题目分析】

用1*2的牌铺满n*m的格子。

刚开始用到动规想写一个n*m*2^m，写了半天才知道会有重复的情况。

So Sad。

然后想到数据范围这么小，爆搜好了。于是把每一种状态对应的转移都搜了出来。

加了点优（gou）化（pi），然后poj上1244ms垫底。

大概的方法就是考虑每一层横着放的情况，剩下的必须竖起来的情况到下一层取反即可。

然后看了《插头DP-从入门到跳楼》这篇博客，怒抄插头DP

然后16ms了，自己慢慢YY了一下，写出了风（gou）流（pi）倜（bu）傥（tong）的代码

UPD：发现完全不需要轮廓线，直接把轮廓线断开一小段就可以转移了，更加坚定自己的算法渣了

【代码】

状压DP

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

ll dp[12][1<<12];

int pos[12],n,m,to[1<<12];

void print(int x){F(i,0,m-1)printf("%d",(x>>i)&1);}

void dfs(int x)

{

	if (to[x]) return ;

	to[x]=1;

	F(i,0,m-2)

		if ((!(x&pos[i]))&&(!(x&pos[i+1])))

			dfs(x|pos[i]+pos[i+1]);

}

int main()

{

	while (scanf("%d%d",&n,&m)!=EOF&&n&&m)

	{

		memset(dp,0,sizeof dp); int all=(1<<m)-1;

		F(i,0,m) pos[i]=1<<i; dp[0][(1<<m)-1]=1;

		F(i,0,n-1)

		{

			F(j,0,(1<<m)-1)

			{

				memset(to,0,sizeof to);

				int aim=j^all; dfs(aim);

				F(k,0,(1<<m)-1)

					if (to[k]) dp[i+1][k]+=dp[i][j];

			}

		}

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

	}

}

　　插头DP

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;  

long long dp[2][1<<11];  

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m),(n||m))

    {

        int total=1<<m;

        int pre=0,now=1;

        memset(dp[now],0,sizeof(dp[now]));

        dp[now][0]=1;  

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

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

        {

            swap(now,pre);

            memset(dp[now],0,sizeof(dp[now]));  

            for(int S=0;S<total;S++) if( dp[pre][S] )

            {

                dp[now][S^(1<<j)]+=dp[pre][S];

                if( j && S&(1<<(j-1)) && !(S&(1<<j)) )

                    dp[now][S^(1<<(j-1))]+=dp[pre][S];

            }

        }  

        printf("%lld\n",dp[now][0]);

    }

}

　　自己写的代（gou）码（pi）

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long

#define F(i,j,k) for (int i=j;i<=k;++i)

ll dp[2][1<<12];

int n,m;

void print(int x)

{F(i,0,m)printf("%d",(x>>i)&1);}

int main()

{

	while (scanf("%d%d",&n,&m)!=EOF&&n&&m)

	{

		if (n<m) swap(n,m);

		int now=1,pre=0;

		memset(dp[now],0,sizeof dp[now]);

		dp[now][0]=1;

		F(i,0,n-1)

			F(j,0,m-1)

			{

				now^=1;pre^=1;

				memset(dp[now],0,sizeof dp[now]);

				F(s,0,(1<<(m+1))-1) if (dp[pre][s])

				{

					if ((s&(1<<j))&&!(s&(1<<(j+1)))) dp[now][s^(1<<j)]+=dp[pre][s];

					if (!(s&(1<<j))&&!(s&(1<<(j+1)))) dp[now][s^(1<<j)]+=dp[pre][s],dp[now][s^(1<<(j+1))]+=dp[pre][s];

					if (!(s&(1<<j))&&(s&(1<<(j+1)))) dp[now][s^(1<<(j+1))]+=dp[pre][s];

				}

				if (j==m-1)

				{

					now^=1;pre^=1;

					memset(dp[now],0,sizeof dp[now]);

					F(s,0,(1<<m)-1) if (dp[pre][s]&&!(s&(1<<m)))

						dp[now][(s<<1)&((1<<(m+1))-1)]+=dp[pre][s];

				}

			}

		printf("%lld\n",dp[now][0]);

	}

}

巴特西

POJ 2411 Mondriaan's Dream ——状压DP 插头DP

最新文章

热门文章