【POJ2411】Mondriaan's Dream(动态规划)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 04 日

discuss里看到的牛B方法。。。。短小精悍,看到后十分汗颜,就像做TC样。自己写老长的代码,跟排名前几的代码一比就像dog shit。要走的路还遥遥无期,根本没头啊~~~~。留下大家也观摩下吧。。。
------------------------------
用2进制的01表示不放还是放
第i行只和i-1行有关
枚举i-1行的每个状态,推出由此状态能达到的i行状态
如果i-1行的出发状态某处未放,必然要在i行放一个竖的方块,所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态。
然后用搜索扫一道在i行放横着的方块的所有可能,并且把这些状态累加上i-1的出发状态的方法数,如果该方法数为0,直接continue。
举个例子
2 4
1111
1111
状态可以由
1100 0000 0110 0011 1111
0000 0000 0000 0000 0000
这五种i-1的状态达到,故2 4 的答案为5

#include<cstdio>
#include<cstring>
long long f[30][1<<12],i,j,height,width,saya=1;
void sayatime (int i,int s1,int pos){
	if (pos==width) {f[i][s1]+=saya;return;}
	sayatime(i,s1,pos+1);
	if (pos<=width-2&&!(s1&1<<pos)&&!(s1&1<<pos+1)) 
		sayatime(i,s1|1<<pos|1<<pos+1,pos+2);
}
int main(){
	freopen("1.txt","r",stdin);
	while(scanf("%d%d",&height,&width),height!=0){
		memset(f,0,sizeof(f));saya=1;
		sayatime(1,0,0);
		for (i=2;i<=height;i++)
			for (j=0;j<1<<width;j++){
				if (f[i-1][j]) saya=f[i-1][j]; 
				else continue;
				sayatime(i,~j&((1<<width)-1),0);
			}
		printf("%lld\n",f[height][(1<<width)-1]);
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 12 月 17 日