BZOJ5205 [CodePlus 2018 3 月赛]白金元首与莫斯科

传送门

emm在雅礼集训的时候听到的一道题上来就觉得是插头dp 最后果然是轮廓线状压233

我们简化一下题意。有一个n*m的网格，每个格子是空地或障碍物，询问把每一个空地看成障碍物的情况下，用1*2的骨牌覆盖（可以留有空地）的方案数对1e9+7取模 bzoj和洛咕题面都挂了233

我们发现留有空地就很烦，所以我们可以把空地看成1*1的骨牌，这样的话我们统计的方案数就是用1*1的骨牌和1*2的骨牌完全覆盖网格的方案数。

骨牌覆盖！ ——》轮廓线状压！

但是我们发现如果对于每个格子直接计算的话时间复杂度是O(n^3*2^m) 根本无法承受

所以我们考虑另一种做法我们可以选择对前后缀进行合并这样的话复杂度就降到了O(n^2*2^m)

我们考虑如何对前后缀进行合并即什么样的两条轮廓线是合法的

对应红色的格子作为我们的合并的格子的话首先要求它上下两个格子已经被覆盖过了然后就是上下对应的蓝绿格子应该状态相同这样才能竖着填满棋盘（我们现在只考虑竖着因为横向的覆盖是在轮廓线dp的时候已经讨论过了）

所以我们对前后分别进行一次轮廓线dp（讨论横着放1*2竖着放1*2放1*1和不放）然后最后统计答案的时候进行合并即可

附代码。（哦对bzoj卡空间只能开到1<<17不过也够了233）

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define inf 20021225

#define ll long long

#define mdn 1000000007

using namespace std;

int f[18][18][1<<17],g[18][18][1<<17];

int bit[18],n,m,top;

int mp[18][18];

void add(int &x,int y){x=(x+y)%mdn;}

void work()

{

	//int top=(1<<m)-1;

	f[1][1][top]=1;

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

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

	{

		int x=i,y=j+1;

		if(j==m)	x=i+1,y=1;

		if(x>n)	continue;

		for(int st=0;st<=top;st++)

			if(f[i][j][st])

			{

				int tmp=f[i][j][st];

				if((st&bit[j])==0&&mp[i][j])	continue;

				if((st&bit[j])==0)

				{

					add(f[x][y][st|bit[j]],tmp);

					continue;

				}

				if(mp[i][j])	add(f[x][y][st],tmp);

				else

				{

					add(f[x][y][st],tmp);

					add(f[x][y][st^bit[j]],tmp);

					if(j>1&&(st&bit[j-1])==0)	add(f[x][y][st|bit[j-1]],tmp);

				}

			}

	}

	g[n][m][top]=1;

	for(int i=n;i;i--)

	for(int j=m;j;j--)

	{

		int x=i,y=j-1;

		if(j==1)	x=i-1,y=m;

		if(x<1)	continue;

		for(int st=0;st<=top;st++)

			if(g[i][j][st])

			{

				int tmp=g[i][j][st];

				if((st&bit[j])==0&&mp[i][j])	continue;

				//printf("%d %d %d %d\n",i,j,st,g[i][j][st]);

				if((st&bit[j])==0)

				{

					add(g[x][y][st|bit[j]],tmp);

					continue;

				}

				if(mp[i][j])	add(g[x][y][st],tmp);

				else

				{

					add(g[x][y][st],tmp);

					add(g[x][y][st^bit[j]],tmp);

					if(j<m&&(st&bit[j+1])==0)	add(g[x][y][st|bit[j+1]],tmp);

				}

			}

	}

}

int main()

{

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

	bit[1]=1;top=(1<<m)-1;

	for(int i=2;i<=m;i++)	bit[i]=bit[i-1]<<1;

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

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

			scanf("%d",&mp[i][j]);

	work();

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

	{

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

		{

			if(mp[i][j])

			{

				printf("0 ");

				continue;

			}

			int ans=0;

			for(int s=0;s<=top;s++)

			{

				if(s&bit[j])

					add(ans,(ll)f[i][j][s]*g[i][j][s]%mdn);

				//printf("%d %d %d %d\n",i,j,f[i][j][s],g[i][j][s]);

			}

			printf("%d ",ans);

		}

		printf("\n");

	}

	return 0;

}

巴特西

BZOJ5205 [CodePlus 2018 3 月赛]白金元首与莫斯科

传送门

最新文章

热门文章