9
4
2015
1

【轮廓线状压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: 985
AP 10th Evs Model Pa 说:
2022年9月19日 00:57

Advised to everyone can contact the class teacher to get important questions for all lessons and topics of EVS. Every Telugu Medium, English Medium and Urdu Medium student of the State Board can download the AP 10th Class EVS Model Paper 2023 Pdf with answers for term-1 & term-2 exams of SA-1, SA-2 and other exams of the board. AP 10th Evs Model Paper Environmental Education is one of the most important subjects and it’s a part of Science. School Education Department and various leading private school teaching staff have designed and suggested the practice question paper for all Part-A, Part-B, Part-C, and Part-D questions of SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 and Assignments.


登录 *


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