Flandre Scarlet's Blog

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)₂，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;
}

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