注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【Wiki1050】【DP】【补档】棋盘染色  

2014-04-29 19:05:25|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好久之前A的题……还是蛮经典的
因为题解很少所以发上来
据说可以骗访问量
其实我也是看兰多夫87神犇的题解

状压DP
枚举上次的状态(联通情况)
然后再枚举当前行放或不放,从而得到当前行的联通情况
注意只有上一行的联通块全部连到当前行时才能转移
从上开始转移到某行下面没有块就停止得到答案
我一开始没有认真读题……以为数据是从左往右延伸,WA了好长时间QAQ
应该是第一次写基于连通性的状压dp……

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int max(int a,int b){if(a>b)return a;return b;}
int min(int a,int b){if(a<b)return a;return b;}
const int _MAX = 1000000000+1;
const int N = 100+1;
int n,m,ans,four[6],now,end;
int map[N][6],jc[N][6],f[N][1025];
short lin[6],lin2[6],lin1[6],lin3[6];
int calc4(short *t){
	int i,j,re=0;;
	for(i=1;i<=5;i++)
		re+=t[i]*four[i-1];
	return re;
}
void bh(int x,int b){//1->lin1 2->lin3
	if(lin3[x]||lin2[x]==0) return;
	while(lin2[x-1]==1&&x>1) x--;
	for(int i=x;i<=5&&lin2[i];i++)
		lin3[i]=b;
	for(int i=x;i<=5&&lin2[i];i++){//down
		if(lin[i])
		for(int j=i;j<=5;j++)
		if(lin[j]==lin[i]){
			bh(j,b);
		}
	}
}
void dfs2(int x){
	int i,j;
	if(x > 5){
		short bhn=0;lin3[0]=0;
		int last = calc4(lin),nowans;
		if(last==277&&now==4){
			//printf("pause\n");
		}
		//check 保证之前的联通块都和目前的状态有连接 
		if(lin[0]>=1){
			short v[6];memset(v,0,sizeof(v));
			for(i=1;i<=5;i++)
			if(lin2[i])
				v[lin[i]]=1;
			for(i=1;i<=lin[0];i++)
				if(!v[i]) return;//不合法 
		}
		//calc last
		nowans = f[now-1][last]+lin2[0];
		//update ans
		lin3[0]=lin[0];
		memset(lin3,0,sizeof(lin3));
		//给当前连通编号
		for(i=1;i<=5;i++)
		if(lin2[i]&&(!lin3[i])){//down
			bh(i,++bhn);
		}
		//update now
		if(now==end&&bhn<=1){
			ans=min(nowans,ans);
		}
		int nown = calc4(lin3);
		f[now][nown] = min(f[now][nown],nowans);
		return;
	}
	if(!map[now][x]){
		for(i=0;i<2;i++){
			lin2[x]=i;
			if(i==1) lin2[0]++;//放的个数 
			dfs2(x+1);
			if(i==1) lin2[0]--;
		}
	}else{
		lin2[x]= 1;
		dfs2(x+1);
	}
}
void dfs1(int x){
	int save=lin[0];
	if(x>5){
		//find now
		int last = calc4(lin);
		if(f[now-1][last]==_MAX) return;
		dfs2(1);
		return;
	}
	//Last
	for(int i=0;i<4;i++){
		if(i==0 && map[now-1][x]) continue;
		if(i>lin[0]+1)continue;
		lin[0]=max(lin[0],i);
		lin[x]=i;
		dfs1(x+1);
		lin[0]=save;
	}
}
int main(){
	int i,j;char c;
	scanf("%d",&n);
	four[0]=1;
	for(i=1;i<=5;i++)
		four[i]=four[i-1]*4;
	for(i=0;i<=n;i++)
	for(j=0;j<=1024;j++)
		f[i][j]=_MAX;
	f[0][0]=0;
	ans=_MAX;
	for(j=1;j<=n;j++)
	for(i=1;i<=5;i++){
		scanf(" %c",&c);
		if(c=='1') {map[j][i]=1;end = max(end,j);}
	}
	
	if(end==0) {printf("0\n");return 0;}
	for(i=1;i<=end;i++){
		now=i;
		dfs1(1);
	}
	printf("%d",ans);
	return 0;
}
  评论这张
 
阅读(35)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017