【POJ2411】Mondriaan's Dream（轮廓线DP）

题面

Vjudge

题解

这题我会大力状压！！！

时间复杂度大概是\(O(2^{2n}n^2)\)，设\(f[i][S]\)表示当前第\(i\)行向下伸展出去的状态为\(S\)

那么每次枚举一下当前行的放法，进行转移就好了。

然后就长成了这个样子（不要在意我强行缩减代码长度）

尽管这不是我们本题的重点，然而我还是放份代码

#include<cstdio>

#include<cstring>

int n,m;long long f[12][1<<11];

int main()

{

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

	{

		if(n==0)break;memset(f,0,sizeof(f));f[0][0]=1;

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

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

				for(int k=0;k<(1<<m);++k)

				{

					if(j&k)continue;

					int t=j|k;bool fl=true;

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

						if(!(t&(1<<l)))

							{

								if(t&(1<<(l+1))){fl=false;break;}

								if(l==m-1){fl=false;break;}

								t|=1<<l;t|=1<<(l+1);

							}

						if(fl)f[i][k]+=f[i-1][j];

				}

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

	}

}

标题里都写了是轮廓线\(dp\)，那么我们就来轮廓线一下？

我们从上往下，从左往右依次放东西。假设当前填到了位置\((i,j)\)

那么对于当前以及接下来的状态有影响的只有\((i,1..j-1)\)和\((i-1,j..m)\)

一共\(m\)个位置，那么我们把这些位置按照从上往下从左往右的顺序压缩。

考虑如何转移：

1.作为一个竖着放的矩形的下半部分，那么需要\((i-1,j)\)未被覆盖。

2.作为一个横着放的矩形的右半部分，那么需要\((i,j-1)\)未被覆盖。

3.啥都不干，等着后面的格子来覆盖当前位置。

当然，每一项转移都要限制，比如如果当前位置的正上方的位置是空的，那么必须竖着覆盖。

接下来就是大力的转移咯。

#include<cstdio>

#include<cstring>

int n,m;long long f[122][1<<11];

int main()

{

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

	{

		memset(f,0,sizeof(f));f[0][(1<<m)-1]=1;

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

			for(int j=1,nw=i*m-m+j;j<=m;++j,++nw)

				for(int k=0;k<(1<<m);++k)

					if(f[nw-1][k])

					{

						if(i>1&&!(k&1))

							f[nw][(k>>1)|(1<<(m-1))]+=f[nw-1][k];

						if(j>1&&!(k&(1<<(m-1)))&&(k&1))

							f[nw][(k>>1)|(1<<(m-1))|(1<<(m-2))]+=f[nw-1][k];

						if(((k&1)||i==1))

							f[nw][k>>1]+=f[nw-1][k];

					}

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

	}

}