9
4
2015
0

【轮廓线状压DP+伪BFS】Codevs 1050 棋盘染色2

Codevs传送门

题意:给定5*n的黑白棋盘,要求将最少的白格染黑,使黑色块相联通。

娱乐活动w

考虑宽=5非常小,就在宽上做文章。。吧

怎么表示状态woc?状压?

压什么?

作为一名专(sha)业(cha)选手,我选择乱(si)搞(wang)

dp[i,a,b,c,d,e]表示第i行的情况a,b,c,d,e,且保证i行之前没有和待处理行不联通的块的情况下(这句话后面解释),最少的染色数。

a,b,c,d,e记录的一定是联通情况对不对!是不是可以记录联通分量(未联通的“第几块”)!

连通分量最多3个!(10101)

也就是a,b,c,d,e<4.....

状压?两位一压?

S=(abcde)2,dp[i,S]就十分资磁地表示出来了。

相邻两行的转移?

什么情况下能够转移?

刚才状态定义的是什么意思。。

这样的转移显然是资磁的:

11111→
10011

这样的转移显然也是资磁的:

11022→
11002(已染色)

这样转移的显然是不资磁的:

10022→
11000

因为连通块2断子绝孙了233

然而这样转移又是资磁的:

10011→
11000

因为右边连通块1通过左边的1可以传到下面(说明在dp这行之前,上行两边的1已经连通了,比如第一个资磁的例子)。

于是处理连通块我选择宽搜233

那么基本架构出来了:

1、对于某一行a[i],枚举a[i]的生成状态j(由a[i]的某些0换成1的状态,并记录换了几个,作为转移的费用)

2、枚举第i-1行的所有状态k,判断k能否转移到j(BFS)

3、转移。

4、对于最末行枚举全联通状态(也就是非0即1),记录答案

是不是很斯波。。

Code(dp数组采用滚动Q):

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#define INF 2139062143
using namespace std;
int a[110],step[4]={-5,5,-1,1};
struct Poi//不要在意细节
{
	int v[1024];
	Poi(){memset(v,0x7f7f7f7f,sizeof(v));}
	void clear(){memset(v,0x7f7f7f7f,sizeof(v));}
};
Poi Q[2];//轮流决策... 
queue<int>q;
bool ck(int u,int st)
{
	if (u+st<0||u+st>9||(u==4&&st==1)||(u==5&&st==-1)) return 0;
	return 1;
}
int bfs(int a,int b)//无脑弱渣掉智商BFS
{
	int map[10],v[10]={0},cnt=0,cc,vv,vvv[4]={0};
	for (int i=4;i>=0;i--)
		map[i]=a%4,a>>=2,map[5+i]=b%2,b>>=1;
	for (int i=0;i<5;i++)
		if (!v[i]&&map[i])
		{
			cc=map[i];
			if (vvv[cc])vv=2;
			else vv=1,cnt++,vvv[cc]=1;;
			q.push(i);
			v[i]=cnt;
			while (!q.empty())
			{
				int u=q.front();
				if (u>4) vv=0;
				q.pop();
				for (int k=0;k<4;k++)
					if (ck(u,step[k])&&!v[u+step[k]]&&map[u+step[k]])
						v[u+step[k]]=cnt,q.push(u+step[k]);
			}
			if (vv==0) vvv[cc]=2;
		}
	for (int i=1;i<4;i++) if (vvv[i]==1) return -1; 
	for (int i=0;i<5;i++)
		if (!v[5+i]&&map[5+i])
		{
			cnt++;
			q.push(5+i);
			v[5+i]=cnt;
			while (!q.empty())
			{
				int u=q.front();
				q.pop();
				for (int k=0;k<4;k++)
					if (ck(u,step[k])&&!v[u+step[k]]&&map[u+step[k]])
						v[u+step[k]]=cnt,q.push(u+step[k]);
			}
		}
	for (int i=0;i<=4;i++)
		if (!v[i]&&map[i]) return -1; 
	for (int i=0;i<=4;i++)
		b=v[5+i]+(b<<2);
	return b;
}
bool ct(int a,int b,int &e)//Whether b contains a.
{
	if ((b&a)-a) return 0;
	b=b^(b&a),e=0;
	for (int i=0;i<5;i++)
		e+=b&1,b>>=1;
	return 1;
}
int trans(int a)
{
	int b=0;
	for (int i=0;i<5;i++)
	{
		b=(a&1)+(b<<2);
		a>>=1;
	}
	return b;
}
int main()
{
	int n;
	char ch;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("\n");
		for (int j=0;j<5;j++)
		{
			ch=getchar();
			a[i]<<=1;
			if (ch-'0') a[i]+=1;
			else a[i]+=0;
		}
	}
	int c1=0,c2=1,c;//总是c1转移给c2 
	int m=n,ans=INF;
	while (!a[m]) m--;
	Q[c2].v[0]=0;
	for (int i=1;i<=m;i++)
	{
		c1^=1,c2^=1;
		Q[c2].clear();
		for (int j=0;j<(1<<5);j++)
			if (ct(a[i],j,c))//j的状态由a[i]生成
				for (int k=0;k<(1<<10);k++)
					if (Q[c1].v[k]!=INF)//上一层存在k这种情况 
					{
						int w=bfs(k,j);
						if (w==-1) continue;
						Q[c2].v[w]=min(Q[c1].v[k]+c,Q[c2].v[w]);//大力转移 				
					}
	}
	for (int i=0;i<(1<<5);i++)
		ans=min(ans,Q[c2].v[trans(i)]);
	printf("%d",ans);
	return 0;
}

无脑部分总是写得又臭又长求智商支援

Category: Codevs | Tags: 轮廓线状压DP BFS | Read Count: 423

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com