文档章节

题解 UVA11270 【Tiling Dominoes】

o
 osc_g8254g7s
发布于 2019/08/19 22:27
字数 2284
阅读 25
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目链接:Link

Solution

记忆化动态规划 什么鬼

这题是一道典型的插头DP(轮廓线动态规划),由于如果不记录轮廓线无法转移且m和n中至少有一个不超过10,所以可以用二进制编码将轮廓线计入状态,详细推导过程见《算法竞赛入门经典训练指南》P384。

这是裸的插头DP:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=15;
int n,m,pos;
LL d[2][1<<maxn];
inline void update(int a,int b) { if(b&(1<<m)) d[pos][b^(1<<m)]+=d[pos^1][a]; }
int main()
{
#ifdef local
	freopen("pro.in","r",stdin);
#endif
	while(scanf("%d%d",&n,&m)==2)
	{
		if(m>n) swap(n,m);
		memset(d,0,sizeof(d));
		pos=0;
		d[0][(1<<m)-1]=1;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				pos^=1;
				memset(d[pos],0,sizeof(d[pos]));
				for(int k=0;k<(1<<m);k++)
				{
					update(k,k<<1);
					if(i&&!(k&(1<<(m-1)))) update(k,(k<<1)^(1<<m)^1);
					if(j&&!(k&1)) update(k,(k<<1)^3);
				}
			}
		printf("%lld\n",d[pos][(1<<m)-1]);
	}
	return 0;
}

TLE4次后一怒之下交了个表:

#include<cstdio>
long long res[105][105];
int main()
{
#ifdef local
	freopen("pro.in","r",stdin);
#endif
	res[1][1]=res[1][1]=0ll;
	res[1][2]=res[2][1]=1ll;
	res[1][3]=res[3][1]=0ll;
	res[1][4]=res[4][1]=1ll;
	res[1][5]=res[5][1]=0ll;
	res[1][6]=res[6][1]=1ll;
	res[1][7]=res[7][1]=0ll;
	res[1][8]=res[8][1]=1ll;
	res[1][9]=res[9][1]=0ll;
	res[1][10]=res[10][1]=1ll;
	res[1][11]=res[11][1]=0ll;
	res[1][12]=res[12][1]=1ll;
	res[1][13]=res[13][1]=0ll;
	res[1][14]=res[14][1]=1ll;
	res[1][15]=res[15][1]=0ll;
	res[1][16]=res[16][1]=1ll;
	res[1][17]=res[17][1]=0ll;
	res[1][18]=res[18][1]=1ll;
	res[1][19]=res[19][1]=0ll;
	res[1][20]=res[20][1]=1ll;
	res[1][21]=res[21][1]=0ll;
	res[1][22]=res[22][1]=1ll;
	res[1][23]=res[23][1]=0ll;
	res[1][24]=res[24][1]=1ll;
	res[1][25]=res[25][1]=0ll;
	res[1][26]=res[26][1]=1ll;
	res[1][27]=res[27][1]=0ll;
	res[1][28]=res[28][1]=1ll;
	res[1][29]=res[29][1]=0ll;
	res[1][30]=res[30][1]=1ll;
	res[1][31]=res[31][1]=0ll;
	res[1][32]=res[32][1]=1ll;
	res[1][33]=res[33][1]=0ll;
	res[1][34]=res[34][1]=1ll;
	res[1][35]=res[35][1]=0ll;
	res[1][36]=res[36][1]=1ll;
	res[1][37]=res[37][1]=0ll;
	res[1][38]=res[38][1]=1ll;
	res[1][39]=res[39][1]=0ll;
	res[1][40]=res[40][1]=1ll;
	res[1][41]=res[41][1]=0ll;
	res[1][42]=res[42][1]=1ll;
	res[1][43]=res[43][1]=0ll;
	res[1][44]=res[44][1]=1ll;
	res[1][45]=res[45][1]=0ll;
	res[1][46]=res[46][1]=1ll;
	res[1][47]=res[47][1]=0ll;
	res[1][48]=res[48][1]=1ll;
	res[1][49]=res[49][1]=0ll;
	res[1][50]=res[50][1]=1ll;
	res[1][51]=res[51][1]=0ll;
	res[1][52]=res[52][1]=1ll;
	res[1][53]=res[53][1]=0ll;
	res[1][54]=res[54][1]=1ll;
	res[1][55]=res[55][1]=0ll;
	res[1][56]=res[56][1]=1ll;
	res[1][57]=res[57][1]=0ll;
	res[1][58]=res[58][1]=1ll;
	res[1][59]=res[59][1]=0ll;
	res[1][60]=res[60][1]=1ll;
	res[1][61]=res[61][1]=0ll;
	res[1][62]=res[62][1]=1ll;
	res[1][63]=res[63][1]=0ll;
	res[1][64]=res[64][1]=1ll;
	res[1][65]=res[65][1]=0ll;
	res[1][66]=res[66][1]=1ll;
	res[1][67]=res[67][1]=0ll;
	res[1][68]=res[68][1]=1ll;
	res[1][69]=res[69][1]=0ll;
	res[1][70]=res[70][1]=1ll;
	res[1][71]=res[71][1]=0ll;
	res[1][72]=res[72][1]=1ll;
	res[1][73]=res[73][1]=0ll;
	res[1][74]=res[74][1]=1ll;
	res[1][75]=res[75][1]=0ll;
	res[1][76]=res[76][1]=1ll;
	res[1][77]=res[77][1]=0ll;
	res[1][78]=res[78][1]=1ll;
	res[1][79]=res[79][1]=0ll;
	res[1][80]=res[80][1]=1ll;
	res[1][81]=res[81][1]=0ll;
	res[1][82]=res[82][1]=1ll;
	res[1][83]=res[83][1]=0ll;
	res[1][84]=res[84][1]=1ll;
	res[1][85]=res[85][1]=0ll;
	res[1][86]=res[86][1]=1ll;
	res[1][87]=res[87][1]=0ll;
	res[1][88]=res[88][1]=1ll;
	res[1][89]=res[89][1]=0ll;
	res[1][90]=res[90][1]=1ll;
	res[1][91]=res[91][1]=0ll;
	res[1][92]=res[92][1]=1ll;
	res[1][93]=res[93][1]=0ll;
	res[1][94]=res[94][1]=1ll;
	res[1][95]=res[95][1]=0ll;
	res[1][96]=res[96][1]=1ll;
	res[1][97]=res[97][1]=0ll;
	res[1][98]=res[98][1]=1ll;
	res[1][99]=res[99][1]=0ll;
	res[1][100]=res[100][1]=1ll;
	res[2][2]=res[2][2]=2ll;
	res[2][3]=res[3][2]=3ll;
	res[2][4]=res[4][2]=5ll;
	res[2][5]=res[5][2]=8ll;
	res[2][6]=res[6][2]=13ll;
	res[2][7]=res[7][2]=21ll;
	res[2][8]=res[8][2]=34ll;
	res[2][9]=res[9][2]=55ll;
	res[2][10]=res[10][2]=89ll;
	res[2][11]=res[11][2]=144ll;
	res[2][12]=res[12][2]=233ll;
	res[2][13]=res[13][2]=377ll;
	res[2][14]=res[14][2]=610ll;
	res[2][15]=res[15][2]=987ll;
	res[2][16]=res[16][2]=1597ll;
	res[2][17]=res[17][2]=2584ll;
	res[2][18]=res[18][2]=4181ll;
	res[2][19]=res[19][2]=6765ll;
	res[2][20]=res[20][2]=10946ll;
	res[2][21]=res[21][2]=17711ll;
	res[2][22]=res[22][2]=28657ll;
	res[2][23]=res[23][2]=46368ll;
	res[2][24]=res[24][2]=75025ll;
	res[2][25]=res[25][2]=121393ll;
	res[2][26]=res[26][2]=196418ll;
	res[2][27]=res[27][2]=317811ll;
	res[2][28]=res[28][2]=514229ll;
	res[2][29]=res[29][2]=832040ll;
	res[2][30]=res[30][2]=1346269ll;
	res[2][31]=res[31][2]=2178309ll;
	res[2][32]=res[32][2]=3524578ll;
	res[2][33]=res[33][2]=5702887ll;
	res[2][34]=res[34][2]=9227465ll;
	res[2][35]=res[35][2]=14930352ll;
	res[2][36]=res[36][2]=24157817ll;
	res[2][37]=res[37][2]=39088169ll;
	res[2][38]=res[38][2]=63245986ll;
	res[2][39]=res[39][2]=102334155ll;
	res[2][40]=res[40][2]=165580141ll;
	res[2][41]=res[41][2]=267914296ll;
	res[2][42]=res[42][2]=433494437ll;
	res[2][43]=res[43][2]=701408733ll;
	res[2][44]=res[44][2]=1134903170ll;
	res[2][45]=res[45][2]=1836311903ll;
	res[2][46]=res[46][2]=2971215073ll;
	res[2][47]=res[47][2]=4807526976ll;
	res[2][48]=res[48][2]=7778742049ll;
	res[2][49]=res[49][2]=12586269025ll;
	res[2][50]=res[50][2]=20365011074ll;
	res[3][3]=res[3][3]=0ll;
	res[3][4]=res[4][3]=11ll;
	res[3][5]=res[5][3]=0ll;
	res[3][6]=res[6][3]=41ll;
	res[3][7]=res[7][3]=0ll;
	res[3][8]=res[8][3]=153ll;
	res[3][9]=res[9][3]=0ll;
	res[3][10]=res[10][3]=571ll;
	res[3][11]=res[11][3]=0ll;
	res[3][12]=res[12][3]=2131ll;
	res[3][13]=res[13][3]=0ll;
	res[3][14]=res[14][3]=7953ll;
	res[3][15]=res[15][3]=0ll;
	res[3][16]=res[16][3]=29681ll;
	res[3][17]=res[17][3]=0ll;
	res[3][18]=res[18][3]=110771ll;
	res[3][19]=res[19][3]=0ll;
	res[3][20]=res[20][3]=413403ll;
	res[3][21]=res[21][3]=0ll;
	res[3][22]=res[22][3]=1542841ll;
	res[3][23]=res[23][3]=0ll;
	res[3][24]=res[24][3]=5757961ll;
	res[3][25]=res[25][3]=0ll;
	res[3][26]=res[26][3]=21489003ll;
	res[3][27]=res[27][3]=0ll;
	res[3][28]=res[28][3]=80198051ll;
	res[3][29]=res[29][3]=0ll;
	res[3][30]=res[30][3]=299303201ll;
	res[3][31]=res[31][3]=0ll;
	res[3][32]=res[32][3]=1117014753ll;
	res[3][33]=res[33][3]=0ll;
	res[4][4]=res[4][4]=36ll;
	res[4][5]=res[5][4]=95ll;
	res[4][6]=res[6][4]=281ll;
	res[4][7]=res[7][4]=781ll;
	res[4][8]=res[8][4]=2245ll;
	res[4][9]=res[9][4]=6336ll;
	res[4][10]=res[10][4]=18061ll;
	res[4][11]=res[11][4]=51205ll;
	res[4][12]=res[12][4]=145601ll;
	res[4][13]=res[13][4]=413351ll;
	res[4][14]=res[14][4]=1174500ll;
	res[4][15]=res[15][4]=3335651ll;
	res[4][16]=res[16][4]=9475901ll;
	res[4][17]=res[17][4]=26915305ll;
	res[4][18]=res[18][4]=76455961ll;
	res[4][19]=res[19][4]=217172736ll;
	res[4][20]=res[20][4]=616891945ll;
	res[4][21]=res[21][4]=1752296281ll;
	res[4][22]=res[22][4]=4977472781ll;
	res[4][23]=res[23][4]=14138673395ll;
	res[4][24]=res[24][4]=40161441636ll;
	res[4][25]=res[25][4]=114079985111ll;
	res[5][5]=res[5][5]=0ll;
	res[5][6]=res[6][5]=1183ll;
	res[5][7]=res[7][5]=0ll;
	res[5][8]=res[8][5]=14824ll;
	res[5][9]=res[9][5]=0ll;
	res[5][10]=res[10][5]=185921ll;
	res[5][11]=res[11][5]=0ll;
	res[5][12]=res[12][5]=2332097ll;
	res[5][13]=res[13][5]=0ll;
	res[5][14]=res[14][5]=29253160ll;
	res[5][15]=res[15][5]=0ll;
	res[5][16]=res[16][5]=366944287ll;
	res[5][17]=res[17][5]=0ll;
	res[5][18]=res[18][5]=4602858719ll;
	res[5][19]=res[19][5]=0ll;
	res[5][20]=res[20][5]=57737128904ll;
	res[6][6]=res[6][6]=6728ll;
	res[6][7]=res[7][6]=31529ll;
	res[6][8]=res[8][6]=167089ll;
	res[6][9]=res[9][6]=817991ll;
	res[6][10]=res[10][6]=4213133ll;
	res[6][11]=res[11][6]=21001799ll;
	res[6][12]=res[12][6]=106912793ll;
	res[6][13]=res[13][6]=536948224ll;
	res[6][14]=res[14][6]=2720246633ll;
	res[6][15]=res[15][6]=13704300553ll;
	res[6][16]=res[16][6]=69289288909ll;
	res[7][7]=res[7][7]=0ll;
	res[7][8]=res[8][7]=1292697ll;
	res[7][9]=res[9][7]=0ll;
	res[7][10]=res[10][7]=53175517ll;
	res[7][11]=res[11][7]=0ll;
	res[7][12]=res[12][7]=2188978117ll;
	res[7][13]=res[13][7]=0ll;
	res[7][14]=res[14][7]=90124167441ll;
	res[8][8]=res[8][8]=12988816ll;
	res[8][9]=res[9][8]=108435745ll;
	res[8][10]=res[10][8]=1031151241ll;
	res[8][11]=res[11][8]=8940739824ll;
	res[8][12]=res[12][8]=82741005829ll;
	res[9][9]=res[9][9]=0ll;
	res[9][10]=res[10][9]=14479521761ll;
	res[9][11]=res[11][9]=0ll;
	res[10][10]=res[10][10]=258584046368ll;
	int n,m;
	while(scanf("%d%d",&n,&m)==2) printf("%lld\n",res[n][m]);
	return 0;
}

然后就过了。

小心输入有大量重复数据!!!

小心输入有大量重复数据!!!

小心输入有大量重复数据!!!

正解应该是在每一次DP之前判断当前这个数据是否计算过,是则直接查表输出,否则将结果加入表中并输出。

正解:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=15;
int n,m,pos;
LL d[2][1<<maxn];
inline void update(int a,int b) { if(b&(1<<m)) d[pos][b^(1<<m)]+=d[pos^1][a]; }
LL res[105][105];
int main()
{
#ifdef local
	freopen("pro.in","r",stdin);
#endif
	memset(res,-1,sizeof(res));
	while(scanf("%d%d",&n,&m)==2)
	{
		if(m>n) swap(n,m);
		if(res[n][m]>-1) { printf("%lld\n",res[n][m]); continue; }
		memset(d,0,sizeof(d));
		pos=0;
		d[0][(1<<m)-1]=1;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				pos^=1;
				memset(d[pos],0,sizeof(d[pos]));
				for(int k=0;k<(1<<m);k++)
				{
					update(k,k<<1);
					if(i&&!(k&(1<<(m-1)))) update(k,(k<<1)^(1<<m)^1);
					if(j&&!(k&1)) update(k,(k<<1)^3);
				}
			}
		printf("%lld\n",res[n][m]=d[pos][(1<<m)-1]);
	}
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

【软件工具篇02】使用Anki克服遗忘曲线

使用Anki克服遗忘曲线 艾宾浩斯遗忘曲线 百度百科:遗忘曲线由德国心理学家艾宾浩斯研究发现,描述了人类大脑对新事物遗忘的规律。人体大脑对新事物遗忘的循序渐进的直观描述,人们可以从遗...

osc_wobxrheh
20分钟前
0
0
面向对象的理解

面向对象的三大特性 封装 继承 多态 面向对象的七大原则 单一职责原则:每一个类应该专注于做一件事情。即高内聚,低耦合。类的功能要单一,体积不要过于庞大。 开闭原则:一个对象对扩展开发...

osc_2wq8ft8d
21分钟前
11
0
Laravel Redis分布式锁实现源码分析

首先是锁的抽象类,定义了继承的类必须实现加锁、释放锁、返回锁拥有者的方法。 namespace Illuminate\Cache;abstract class Lock implements LockContract{ use InteractsWithTime;...

osc_2jegjdnw
23分钟前
0
0
【HDFS篇03】HDFS客户端操作 --- 开发环境准备

存储越困难,提取越容易 HDFS客户端操作---开发环境准备 步骤一:编译对应HadoopJar包,配置Hadoop变量 步骤二:创建Maven工程,导入pom依赖 <dependencies><dependency><groupId>ju...

osc_ds5ni1ur
24分钟前
7
0
老板,来瓶辣椒酱

最近网剧《隐秘的角落》非常的火爆,结局反转让人难以预料,但前两天发生了一场堪比史诗级大片的纠纷,纠纷的结局反转让人大跌眼镜,估计是神编剧都写不出来那样的剧本...而引发这场纠纷最核...

osc_1loi8uc4
26分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部