状态压缩动态规划部分习题详解

  • 时间:
  • 来源:互联网
  • 文章标签:

状态压缩动态规划部分习题详解


状压DP部分题目详解

    • 状态压缩动态规划部分习题详解
      • 简介
      • 经典子集类问题
        • 原子弹
      • 最短路与状压DP结合
        • 送礼物
        • P3959宝藏
        • 旅游
      • 经典网格类
        • 铺地砖
        • 一笔画
      • 其他类型
        • 单词
        • 队伍统计

简介

此处记录了一些比较经典或巧妙的简单状压dp题,粗略介绍了做题的一些思路。


经典子集类问题

原子弹

最近,火星研究人员发现了N个强大的原子。他们互相都不一样。
这些原子具有一些性质。当这两个原子碰撞时,其中一个原子会消失,产生大量的能量。
研究人员知道每两个原子在碰撞时的能释放的能量。
你要写一个程序,让它们碰撞之后产生最多的总能量。
输入格式
有多组数据。
每组数据下的第一行是整数N(2 <= N <= 10),这意味着有N个原子:A1到AN。然后下面有N行,每行有N个整数。在第i行中的第j个整数表示当i和j碰撞之后产生的能量,并且碰撞之后j会消失。
所有整数都是正数,且不大于10000。输入以n=0结尾。输入数据不超过500个。
输出格式
输出N个原子碰撞之后产生的最大总能量。
输入/输出例子1
输入:

2 
0 4
1 0
3 
0 20 1 
12 0 1 
1 10 0 
0

输出:

4 
22

f ( S ) f(S) f(S)表示原子集合为 S S S时释放的最大能量,其中 1 1 1表示原子已消失, 0 0 0表示原子未使用。
显然, f ( S ) = max ⁡ i ∈ S , j ∈ S { f ( S − { j } ) + v ( i , j ) , f ( S − { i } ) + v ( j , i ) } f(S) = \max_{i\in S,j\in S}\{f(S-\{j\})+v(i,j),f(S-\{i\})+v(j,i)\} f(S)=iS,jSmax{f(S{j})+v(i,j),f(S{i})+v(j,i)}
其中,函数 v ( i , j ) v(i,j) v(i,j)表示 i i i j j j碰撞且 j j j消失所产生的能量。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int n,map[15][15];
int f[2048],tot;

int main()
{
	while(1)
	{
		scanf("%d",&n);
		if(n == 0) break;
		tot = (1<<n) - 1;
		for(int i = 1;i <= n;i ++)
			for(int j = 1;j <= n;j ++)
				scanf("%d",&map[i][j]);
		for(int i = 0;i <= tot;i ++) f[i] = 0;
		for(int k = 1;k <= tot;k ++)
			for(int i = 0;i < n;i ++)
			{
				int s1 = 1<<i;
				if((s1&k)>0)
					for(int j = i + 1;j < n;j ++)
					{
						int s2 = 1<<j;
						if((s2&k)>0)
						{
							int s3 = k - s1;
							int s4 = k - s2;
							f[k] = max(f[k],f[s3] + map[j+1][i+1]);
							f[k] = max(f[k],f[s4] + map[i+1][j+1]);
						}
					}
			}
		printf("%d\n",f[tot]);
	}
	return 0;
}


最短路与状压DP结合

送礼物

给出一个n行m列的点阵,“.” 表示可通行格子,“#” 表示不可通行格子,
“K” 表示国王的初始位置,“Q”表示王后的位置,“G”表示该格子有一个礼物。
注意:国王、王后、礼物所在的格子可以认为是可通行格子的。
国王从开始位置出发,国王从当前格子可以走到上、下、左、右四个相邻格子,当然前提是可通行格子。
国王从当前格子走到相邻格子的时间是变化的,这取决于国王手头上收集到的礼物的数量,
假如当前国王手头上有y个礼物,那么他从当前格子移动到相邻格子的所用时间是y+1秒。
一旦国王进入某个有礼物的格子,他可以选择取该格子的礼物,也可以选择不取该格子的礼物。
取礼物这个动作可以认为是瞬间完成的,不需要时间。国王想收集到尽量多的礼物送给王后,
但是他到达王后所在的格子不能超过T秒,王后不想等太长时间。
注意:国王在收集礼物的途中可能多次走到相同的格子。
输入格式
第一行:三个整数,n、m、T。 1 ≤ n, m ≤ 50。 1 ≤ T ≤10^9。
接下来是n行m列的点阵。‘G’的数量不超过16。 只有一个国王,一个王后。
输出格式
一个整数,表示国王能送给皇后的礼物的最大数目
输入/输出例子1
输入:

5  7  50
#....G# 
###G### 
#K...Q# 
###.### 
#G..GG#

输出:

4

看到礼物数目范围很小,考虑状压DP,显然在动态规划之前要处理出所有礼物两两之间的最小距离,注意到国王在收集礼物过程中可走到相同的格子,所以暴力给每一个礼物跑一遍单源最短路,手上就得到状态转移的方式。设 f ( i , S ) f(i,S) f(i,S)表示现国王手上的礼物集合为 S S S,且最后一个拿到的礼物是 i i i,可知此时国王站在礼物 i i i处,显然: f ( i , S ) = min ⁡ S ′ ⊆ S , j ∈ S ′ { f ( j , S ′ ) + d i s ( j , i ) × c n t ( S ) } f(i,S) = \min_{S'\sube S,j\in S'}\{f(j,S')+dis(j,i)\times cnt(S)\} f(i,S)=SS,jSmin{f(j,S)+dis(j,i)×cnt(S)}
其中,函数 d i s ( x , y ) dis(x,y) dis(x,y)表示礼物 x x x和礼物 y y y之间的最小距离,函数 c n t ( S ) cnt(S) cnt(S)表示 S S S 1 1 1的个数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>

using namespace std;
const long long inf = 0xfffffffff;
typedef long long ll;
ll n,m,t,d[55][55],dis[55][55],f[66000][25];
int map[55][55],kx,ky,qx,qy,gx[55],gy[55],cnt,s1,ans,tot,num1;
int mark[55][55],nowx,nowy,nx,ny,dx[5] = {0,0,0,1,-1},dy[5] = {0,1,-1,0,0};
bool vis[55][55];
string s;

int cnt1(int x)
{
	int tmp = 0;
	for(int i = 1;i <= cnt;i ++)
		if((x&(1<<(i-1))) > 0)
			tmp ++;
	return tmp;
}

void bfs(int sx,int sy)//跑最短路
{
	memset(vis,0,sizeof(vis));
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= m;j ++)
			d[i][j] = inf;
	queue< pair<int , int > > q;
	vis[sx][sy] = 1;
	d[sx][sy] = 0;
	q.push(make_pair(sx,sy));
	while(!q.empty())
	{
		nowx = q.front().first;
		nowy = q.front().second;
		q.pop();
		vis[nowx][nowy] = 0;
		for(int i = 1;i <= 4;i ++)
		{
			nx = nowx + dx[i];ny = nowy + dy[i];
			if(nx > 0 && nx <= n && ny > 0 && ny <= m )
				if(d[nx][ny] > d[nowx][nowy] + 1 && map[nx][ny] == 1)
				{
					d[nx][ny] = d[nowx][nowy] + 1;
					if(!vis[nx][ny])
					{
						vis[nx][ny] = 1;
						q.push(make_pair(nx,ny));
					}
				}
		}
	}
	for(int i = 0;i <= cnt + 1;i ++)
		dis[mark[sx][sy]][i] = d[gx[i]][gy[i]];
	return ;
}


int main()
{
	memset(mark,128,sizeof(mark));
	//read data
	scanf("%lld%lld%lld",&n,&m,&t);
	for(int i = 1;i <= n;i ++)
	{
		cin >> s;
		for(int j = 0;j < s.size();j ++)
		{
			switch(s[j])
			{
				case '.':
					map[i][j+1] = 1;
					break;
				case '#':
					map[i][j+1] = 0;
					break;
				case 'G':
					cnt ++;
					gx[cnt] = i;gy[cnt] = j + 1;
					mark[i][j+1] = cnt;
					map[i][j+1] = 1;
					break;
				case 'K':
					kx = i;ky = j + 1;
					map[i][j+1] = 1;
 					break;
				case 'Q':
					qx = i;qy = j + 1;
					map[i][j+1] = 1;
					break;
			}
		}
	}
	mark[kx][ky] = 0;mark[qx][qy] = cnt + 1;
	gx[0] = kx;gy[0] = ky;
	gx[cnt + 1] = qx;gy[cnt + 1] = qy;
	for(int i = 0;i <= cnt+1;i ++)
		for(int j = 0;j <= cnt + 1;j ++)
			dis[i][j] = inf;
			
	for(int i = 0;i <= cnt + 1;i ++)//求出两两之间的最短路程
		bfs(gx[i],gy[i]);
	
	tot = 1<<(cnt+1) - 1;
	for(int i = 0;i <= tot;i ++)
		for(int j = 0;j <= cnt+1; j ++)
			f[i][j] = inf;
	for(int i = 1;i <= cnt;i ++)//初始化
		f[(1<<(i-1))][i] = dis[0][i];
	for(int s = 0;s <= tot; s ++)//状压DP
	{
		num1 = cnt1(s);
		for(int i = 1;i <= cnt;i ++)
			if((s&(1<<(i-1))) > 0)
			{
				s1 = s - (1<<(i-1));
				for(int j = 1;j <= cnt;j ++)
					if((s1&(1<<(j-1))) > 0)
						f[s][i] = min(f[s][i],f[s1][j]+dis[j][i]*num1);
			}
	}
	for(int s = 0;s <= tot;s ++)//最后再判断一次,看能否在T内到皇后的地方
	{
		num1 = cnt1(s);
		for(int i = 1;i <= cnt;i ++)
			if((s&(1<<(i-1))) > 0)
			{
				ll sum = f[s][i] + dis[i][cnt+1]*(num1+1);
				if(sum <= t)
					ans = max(ans,num1);
			}
	}
	printf("%d",ans);
	return 0;
}

P3959宝藏

P3959 宝藏
看到宝藏屋的数目很少,又想到状压dp。
考虑到开拓一间新宝藏屋的费用与开拓道路起点有关,并且与最开始免费打通的宝藏屋有关,设 f ( i , j , S ) f(i,j,S) f(i,j,S)表示开发的宝藏屋集合为 S S S,本次开发到 j j j,最开始打通的宝藏屋为 i i i
发现有:
f ( i , j , S ) = min ⁡ k ∈ S , k ≠ j { f ( i , k , S − { j } ) + min ⁡ e : k → j { d i s ( e ) } × g ( i , k ) } f(i,j,S) = \min_{k\in S,k\ne j}\{f(i,k,S-\{j\})+\min_{e:k\rightarrow j}\{dis(e)\}\times g(i,k)\} f(i,j,S)=kS,k=jmin{f(i,k,S{j})+e:kjmin{dis(e)}×g(i,k)}
其中,函数 d i s ( e ) dis(e) dis(e)表示道路 e e e的长度,函数 g ( i , j ) g(i,j) g(i,j)表示从 i i i j j j所经过的宝藏屋的数目。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>

using namespace std;
const long long inf = 0xfffffffff;
typedef long long ll;
ll f[20][5000],g[20][5000][20],ans = inf,num;
int n,m,x,y,z,u,v,s1,tot,map[6000],tmp;
int head[50],cnt;
struct edge{
	int next;
	int to;
	ll val;
}e[10005];

void myinit()
{
	for(int i = 0;i < 20;i ++)
		for(int j = 0;j < 5000;j ++)
			f[i][j] = inf;
	for(int i = 0;i < 20;i ++)
		for(int j = 0;j < 5000;j ++)
			for(int k = 0;k < 20;k ++)
				g[i][j][k] = inf; 
}

void addedge(int from,int to,int v)
{
	cnt ++;
	e[cnt].next = head[from];
	e[cnt].to =to;
	e[cnt].val = v;
	head[from] = cnt;
	
	cnt ++;
	e[cnt].next = head[to];
	e[cnt].to = from;
	e[cnt].val = v;
	head[to] = cnt;

	return ;
}

int main()
{
	myinit();
	scanf("%d%d",&n,&m);
	
	for(int i = 1;i <= n;i ++)
		map[(1<<(i-1))] = i;
	
	for(int i = 1;i <= m;i ++)
	{
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
	}
	
	tot = (1<<n)-1;
	for(int i = 1;i <= n;i ++)//初始化
	{
		f[i][(1<<(i-1))] = 0;
		g[i][(1<<(i-1))][i] = 1;//一边dp一边更新g(i,j)
	}
	
	for(int k = 1;k <= n;k ++)
		for(int s = 0;s <= tot;s ++)
			for(tmp = s;tmp;tmp = (tmp&(tmp-1)) )
			{
				u = map[(tmp&(-tmp))];
				for(int i = head[u];i != 0;i = e[i].next)//枚举出边
				{
					v = e[i].to;
					if((s&(1<<(v-1))) > 0)
					{
						s1 = s - (1<<(v-1));
						num = g[k][s1][u];
						if(f[k][s] > f[k][s1] + e[i].val*num)
						{
							f[k][s] = f[k][s1] + e[i].val*num;
							for(int j = 1;j <= n;j ++) g[k][s][j] = g[k][s1][j];//更新g(i,j)
							g[k][s][v] = num + 1;//更新g(i,j)
						}
					}
				}
			}

	for(int i = 1;i <= n;i ++)
		ans = min(ans,f[i][tot]);
	
	printf("%lld",ans);
	return 0;
}

旅游

有n (n <= 50)个小岛,编号从0到n-1。一开始你在小岛0。岛与岛之间只能用船来摆渡。有f(1 <= f <= 10)个公司提供船票。
每个公司提供的船票有不同的路线,第i个公司有k_i条单向路线,一条路线就是允许你从一个小岛a到另一个小岛b,一张票只能挑一条路线。
这f个公司在n个小岛都设有售票点,但同一个公司的票在不同的小岛可能价格不一样,而在同一个小岛,你买了某个公司j的票,那么你挑j公司任意一条单向线路的费用都是相同的。
现在的任务是:从小岛0到其它各个小岛的最小费用是多少?
不过还有个麻烦的条件:任意时刻你手上的票不能超过3张,而且同一个公司不能有两张票,也就是说你到了任意一个小岛j,手头上只可能剩0张票或1张票或2张票,而且这些票都是从不同公司买的。
一开始你在小岛0,没有票,出发前最多能买3张票。
如果某个小岛不能到达,那么输出-1。
提示:最小费用路径可能经过同一个城市多次,见样例 2.
输入格式
多组测试数据。
第一行:一个整数r, 表示有r组测试数据。1 <= r <= 3。
每组测试数据格式如下:
第一行:n和f。1 <= n <= 40,1 <= f <= 10。
接下来有f行,第i行描述第i个公司的线路信息,第一整数是k_i(1 <= k_i <= 20),
然后有k_i条单向线路,每条线路就是两个整数a和b,表示公司i有从小岛a到小岛b的路线。
接下来有n行,每行有f个整数,第i行的第j个整数表示在第i个小岛购买第j个公司的一张票的费用,
费用是不超过1000的正整数。
0 <= i < n。1 <= j <= f。
输出格式
共r行,每行n-1个数,表示从小岛0到小岛1的最小费用,小岛0到小岛2的最小费用…小岛0到小岛n-1的最小费用。
输入/输出例子1
输入:

2
5  2
3  0  1  1  2  2  3
2  0  1  2  3
1  10
20  25
50  50
1000  1000
1000  1000
4  4
1  1  0
1  0  1
1  0  2
1  2  3
1  1  1000  1000
1000  1000  10  100
1000  1000  1000  1000
1000  1000  1000  1000 

输出:

1  11  31  -1
1  12  112

样例解释
第一组测试数据解释:
有2个售票公司,5个小岛。第1个公司提供3条单向路线,分别是0到1, 1到2, 2到3。第2个公司提供2条单向路线,分别是0到1,2到3。我们称第一个公司是公司A,第二个公司是公司B。我们在小岛0买一张A公司的票费用是1元,买一张B公司的票费用是10元。在小岛1买一张A公司的票费用是20元,买一张B公司的票费用是25元。在小岛2买一张A公司的票费用是50元,买一张B个公司的票费用是50元。在小岛3买一张A公司的票费用是1000元,买一张B公司的票费用是1000元。在小岛4买一张A公司的票费用是1000元,买一张B公司的票费用是1000元。那么从小岛0到小岛1最小费用是:在小岛0买一张A公司0到1的单向票,费用是1。从小岛0到小岛2最小费用是:在小岛0买一张B公司的0到1的单向票,费用是10,同时还在小岛0买一张A公司的从1到2的单向票,费用是1,那么用11元就可以从小岛0到达小岛2了。 从小岛0到小岛3的最小费用是:在小岛0买一张A公司的0到1的单向票,费用是1,同时在小岛0买一张B公司的2到3的票,费用是10,那么用A公司的票就可以到达小岛1,然后再从小岛1买一张A公司的1到2的单向票费用是20,到了小岛2后在用手头上那张未用的票到达小岛3,总费用是31。小岛4无法到达。
第二组测试数据解释:
设四个公司为A ,B,C,D。
从小岛0到达小岛3的最小费用是: 在小岛0买一张A公司的票和一张B公司的票,用B公司的票到达小岛1,在小岛1买一张C公司的票和一张D公司的票,用A公司的票回到小岛0,现在手头上还有两张票:公司C的票和公司D的票,然后用公司C的票到达小岛2,用公司D的票到达小岛3。

仔细阅读,注意其中几个细节:在任意小岛上都能买任意公司的票;任何时刻手上的票不能超过3张;可多次走同一路线,即可多次去同一个小岛。第一个细节,我们发现对于一种持票情况,某些票可能是来到这个岛之前就买好的,有些票是在这个岛上买的,处理的时候可以分类讨论。第二个细节告诉我们可以预处理出 1 1 1的数量不超过3的所有状态,或者加判断。第三个细节给我们带来不少麻烦,为了保证能够及时更新,我们想到最短路中的更新方法,将队列迁移到dp上来,就能够及时更新状态。设 f ( i , S ) f(i,S) f(i,S)表示在第 i i i个岛上,手里持票情况为 S S S,可以得到:
f ( i , S ) = min ⁡ { min ⁡ k ∈ S 1 , c o n k ( j , i ) = 1 { f ( j , S 1 ) } , min ⁡ k ∈ S { f ( i , S − k ) + p ( k , i ) } } f(i,S) = \min\{\min_{k\in S_1,con_k(j,i)=1}\{f(j,S_1) \},\min_{k\in S}\{f(i,S-{k})+p(k,i)\}\} f(i,S)=min{kS1,conk(j,i)=1min{f(j,S1)},kSmin{f(i,Sk)+p(k,i)}}
其中,函数 c o n k ( x , y ) con_k(x,y) conk(x,y)表示公司 k k k的路线中,是否有一条从 x x x y y y,函数 p ( k , i ) p(k,i) p(k,i)表示公司 k k k的票在 i i i岛上的价格。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>

using namespace std;
const int inf = 2139062143;
int n,cp,k,r,u,v,cnt,f[45][1050],tot,tmp,s1,num;
int map[15][45][45],p[15][45],d[50];
bool vis[50];

int cnt1(int x)
{
	int tmp = 0;
	for(int i = 1;i <= cp;i ++)
		if((x&(1<<(i-1))) > 0)
			tmp ++;
	return tmp;
}

void solve()
{
	//init
	memset(d,127,sizeof(d));
	memset(f,127,sizeof(f));
	memset(map,0,sizeof(map));
	memset(p,0,sizeof(p));
	
	//read
	scanf("%d%d",&n,&cp);
	for(int i = 1;i <= cp;i ++)
	{
		scanf("%d",&k);
		for(int j = 1;j <= k;j ++)
		{
			scanf("%d%d",&u,&v);
			map[i][u][v] = 1;
		}
	}
	for(int i = 0;i < n;i ++)
		for(int j = 1;j <= cp;j ++)
			scanf("%d",&p[j][i]);
	
	//dp
	tot = 1<<(cp+1) - 1;
	for(int i = 0;i <= tot;i ++)//在第一个岛上买票
	{
		num = cnt1(i);
		if(num > 3) continue;
		tmp = 0 ;
		for(int j = 1;j <= cp;j ++)
			if((i&(1<<(j-1))) > 0)
				tmp += p[j][0];
		f[0][i] = tmp;
	}
	
	memset(vis,0,sizeof(vis));
	queue<int > q; 
	q.push(0);
	while(!q.empty())
	{
		int i = q.front();
		q.pop();
		vis[i] = 0;
		for(int s = 0;s <= tot;s ++)//enumrate the status of tickets
		{
			num = cnt1(s);
			if(num > 3) continue;
			for(int j = 1;j <= cp;j ++)//We buy tickets on this island
				if((s&(1<<(j-1))) > 0)
				{
					s1 = s - (1<<(j-1));
					f[i][s] = min(f[i][s],f[i][s1]+p[j][i]);
				}
			for(int j = 1;j <= cp;j ++)//We have bought tickets on other island
				if((s&(1<<(j-1))) > 0)
				{
					s1 = s - (1<<(j-1));
					for(int k = 0;k < n;k ++)
						if(map[j][i][k])//Use this ticket to travel from i to k
						{
							d[k] = min(d[k],f[i][s]);//update the minimum distance
							if(f[k][s1] > f[i][s])//update the next status
							{
								f[k][s1] = f[i][s];
								if(!vis[k])
								{
									vis[k] = 1;
									q.push(k);//keep updating
								}
							}
						}
				}
		}
	}

	for(int i = 1;i < n;i ++)
	{
		if(d[i] == inf) printf("-1 ");
		else printf("%d ",d[i]);
	}
	printf("\n");
}

int main()
{
	scanf("%d",&r);
	for(int i = 1;i <= r;i ++)
		solve();

	return 0;
}

经典网格类

铺地砖

在这里插入图片描述
输入格式
输入包含多个测试用例。
每个测试用例是由两个整数数字:高度h和大型矩形的宽度w。
输入由h = w = 0时终止。否则 1 < = h,w < = 11。
输出格式
每个测试数据输出一个答案。
输入/输出例子1
输入:

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出:

1
0
1
2
3
5
144
51205

考虑用轮廓线,注意横砖一次占两个位,并且注意最后一行不能有突出,详解在参考代码中,注意细节。

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>

using namespace std;
int h,w,tot;
long long f[25][25][30000];
bool vis[25][25][30000];

long long dfs(int x,int y,int s)
{
	if(x > h) return 1;//this rectangle is full of bricks 
	if(y > w) return dfs(x+1,1,s);//next row
	if(vis[x][y][s]) return f[x][y][s];
	vis[x][y][s] = 1;
	int s1 = 1<<(y-1);
	if((s1&s)>0) //the current grid is occupied by a vertical brick
	{
		f[x][y][s] = dfs(x,y+1,s-s1);// As for the next row,it won't be affected by this vertical brick 
		return f[x][y][s];
	}
	long long tmp1 = 0;
	if(x < h)//place a vertical brick on this grid
		tmp1 = dfs(x,y+1,s1+s);//the placement of this brick will influence the way of placing bricks on the next row
	int s2 = 1<<y;long long tmp2 = 0;
	if(y < w)//place a transverse brick on this grid
		if((s2&s)==0)//to check whether we can place this transverse brick or not
			tmp2 = dfs(x,y+1,s+s2);
	f[x][y][s] = tmp1 + tmp2;
	return f[x][y][s];
}

int main()
{
	while(1)
	{
		cin>>h>>w;
		if(h == 0 && w == 0) break;
		tot = (1<<(w+1))-1;
		memset(f,0,sizeof(f));
		memset(vis,0,sizeof(vis));
		cout << dfs(1,1,0) << endl;
	}
	return 0;
}

一笔画

由于小毛同学智商不高,理解不了真正的一笔画问题,于是他就开始研究一种变形的一笔画问题。
给出 n 行 m 列的点阵,每个点是一个字符: “.” 或 “#” ,其中“#”表示该点是障碍物。
现在小毛的问题是: 他最少要画多少笔才能把点阵里所有的“.”都覆盖完毕(被小毛画到的点就会被覆盖)。
小毛的笔有点奇怪:小毛每次只能在某一行或某一列画,小毛当然想一笔就把某一行或某一列画完,
但很遗憾,在任何时候都不允许小毛画的那一段点阵含有障碍物。
还有一点更奇怪: 已经被画过的点,不能重复被画。
输入格式
第一行: n , m 表示点阵行数和列数 。 0 < n, m <=10
接下来有n行, 每行有m个字符,“.” 或 “#”
输出格式
一个整数, 小毛最少要画多少笔。
输入/输出例子1
输入:

2 4
.##.
....

输出:

3

输入/输出例子2
输入:

3  4
....
....
....

输出:

3

看似毫无头绪的搜索,但看到n,m的范围很小,先想想状压dp。
想到#等价于在此格画过,整张图可转化为画过和没画过两种状态,然而这样规定状态导致我们处理的时候无法分清什么时候横着画过,什么时候竖着画过,所以转换思路。
我们将竖着画过的格子标记为 1 1 1,横着画过的格子标记为 0 0 0,遇到不可画格子特判,将每一行的状态转化为 01 01 01串,再仔细想想,情况豁然开朗:

  1. 对于竖着画过的格子,我们要判断上一行同一列的格子是否也竖着画,如果是,这一格就不需要再画一笔
  2. 对于横着画的格子,一个完整连续段算作画一笔
  3. 对于不可画格子,不算作一笔,且一笔横画至此断开

用行列式直接dp即可
f ( i , S ) = min ⁡ S ′ { f ( i − 1 , S ′ ) + g ( S , S ′ ) } f(i,S)=\min_{S'}\{f(i-1,S')+g(S,S')\} f(i,S)=Smin{f(i1,S)+g(S,S)}
其中,函数 g g g表示增加的一笔画次数

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>

using namespace std;
const int inf = 2139062143;
int n,m,f[15][1050],tmp,tmp1,ans = inf,tot,b[15];
//1 refers to drawing vertically and 0 refers to drawing transversely
//regard # as 0 
bool map[15][15],flag;
string s;

bool check(int now,int x)//the position of # in the map can't be 1 in the status
{
	if((b[now]&x) > 0) return 0;
	else return 1;
}

int main()
{
	memset(f,127,sizeof(f));
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i ++)
	{
		cin >> s;
		for(int j = 0;j < s.size();j ++)
			if(s[j] == '#')
			{
				map[i][j+1] = 1;
				b[i] += (1<<j);//record the status
			}
	}
	
	tot = 1<<(m+1) - 1;
	for(int s = 0;s <= tot; s++)//initalization
	{
		if(!check(1,s)) continue;
		flag = 0;tmp = 0;
		for(int j = 1;j <= m;j ++)
		{
			if((s&(1<<(j-1))) > 0)//draw vertically
			{
				tmp ++;
				flag = 0;
			}
			else
			{
				if(map[1][j])
				{
					flag = 0;
					continue;
				}//draw transeversely
				if(flag) continue;//draw with one stroke 
				else
				{
					flag = 1;
					tmp ++;
				}
			}
		}
		f[1][s] = tmp;
		if(1 == n) ans = min(ans,f[1][s]);
	}
	
	for(int i = 2;i <= n;i ++)
	{
		for(int s = 0;s <= tot;s ++)//the status of last row
		{
			if(!check(i-1,s)) continue;
			for(int s1 = 0;s1 <= tot;s1 ++)//the status of this row
			{
				if(!check(i,s1)) continue;
				flag = 0;tmp = 0;tmp1 = 0;
				for(int j = 1;j <= m;j ++)
				{
					if((s1&(1<<(j-1))) > 0)
					{
						flag = 0;
						//draw transeversely on the last row
						if((s&(1<<(j-1))) == 0) tmp1 ++;//draw vertically this row
					}
					else
					{
						if(map[i][j])
						{
							flag = 0;
							continue;
						}
						if(flag) continue;
						else flag = 1,tmp ++;
					}
				}
				f[i][s1] = min(f[i][s1],f[i-1][s] + tmp1 + tmp);
//				cout << i << ' ' << s1 << ' ' << f[i][s1] << endl;
				if(i == n) ans = min(ans,f[i][s1]);
			}
		}
	}
	if(ans == inf) printf("0");
	else printf("%d",ans);
	return 0;
}

其他类型

单词

在这里插入图片描述
输入格式在这里插入图片描述
输出格式
在这里插入图片描述
输入/输出例子1
输入:

3
a
ab
abc

输出:

4

输入/输出例子2
输入:

3
a
ab
c

输出:

4

输入/输出例子3
输入:

4
baab
abab
aabb
bbaa

输出:

5

当所有字符串变换成使得它们的公共前缀最长时,trie树的结点树最少
看到数据范围 1 ≤ n ≤ 16 1\le n\le 16 1n16,自然先想到状压DP
由于字符串可以任意变换,只需统计字符串中每一种字母出现的个数就可以方便表示字符串,且方便接下来的操作
S S S表示被选取加入trie树的字符串的集合, S ′ ⊆ S S'\subseteq S SS f ( S ) f(S) f(S)表示在状态 S S S下trie树的最少结点数, p ( S ) p(S) p(S)表示在 S S S状态下,最大公共前缀的长度
则有: f ( S ) = f ( S ′ ) + f ( S − S ′ ) − p ( S ) f(S) = f(S')+f(S-S')-p(S) f(S)=f(S)+f(SS)p(S)
其中,函数 p ( S ) p(S) p(S)表示在字符串集合为 S S S的情况下的最大公共前缀的长度

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<fstream>

using namespace std;
const int inf = 0xfffffff;
int n,f[65540],tmp,tot,cnt[65540][30];
string s[25];

int main()
{
//	freopen("test.txt","r",stdin);
	cin >> n;
	tot = (1<<n)-1;
	for(int i = 0; i <= tot;i ++) f[i] = inf;
	for(int i = 0;i <= tot;i ++)
		for(int j = 0;j < 26;j ++)
			cnt[i][j] = inf ;
	for(int i = 1;i <= n;i ++)
	{
		cin >> s[i];
		tmp = 1<<(i-1);
		f[tmp] = s[i].size();
		for(int j = 0;j < 26;j ++) cnt[tmp][j] = 0;
		for(int j = 0;j < s[i].size();j ++) cnt[tmp][s[i][j]-'a'] ++;//统计字母
	} 
	f[0] = 0;
	for(int i = 1;i <= tot;i ++)
	{
		tmp = 0;
		for(int j = 1;j <= n;j ++)
			if(((1<<(j-1))&i) > 0)
				for(int k = 0;k < 26;k ++)
					cnt[i][k] = min(cnt[i][k],cnt[(1<<(j-1))][k]);求公共前缀长度
		for(int k = 0;k < 26;k ++)
			tmp += cnt[i][k];
		for(int j = i&(i-1);j;j = (j-1)&i)
		{
			int k = i - j;
			f[i] = min(f[i],f[k]+f[j]-tmp);
		}
	}
	cout << f[tot]+1 << endl;//最后还有空结点
	return 0;
}

队伍统计

在这里插入图片描述
n<=20,又是状压DP
f ( i , S ) f(i,S) f(i,S)表集合 S S S中的人已经排好队,排列合法且队尾是 i i i,则有:
f ( i , S ) = ∑ S ′ ⊆ S , j ∈ S c n t ( S ′ ) < k f ( j , S ′ ) f(i,S)=\sum_{S'\sube S,j\in S}^{cnt(S')<k}f(j,S') f(i,S)=SS,jScnt(S)<kf(j,S)
其中,函数 c n t ( S ) cnt(S) cnt(S)表示 S S S中的矛盾关系个数

#include<iostream>
#include<cstdio>

using namespace std;
const int modnum = 1000000007;
int n,m,k,tot,s1;
int u[505],v[505],tmp;
bool map[30][30];
long long f[35][1048580],ans;

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	tot = (1 << n) - 1;
	for(int i = 1;i <= m;i ++)
	{
		scanf("%d%d",&u[i],&v[i]);
		map[u[i]][v[i]] = 1;
	}
	f[0][0] = 1;
	for(int s = 1; s <= tot; s ++)//enumerate all the states
		for(int i = 1;i <= n;i ++)//enumerate the last number in this sequence
		{
			tmp = 0;
			if(((1<<(i-1))&s) > 0)
			{
				s1 = s - (1<<(i-1));
				
				for(int j = 1;j <= n;j ++)
					if(((1<<(j-1))&s1) > 0)
					{
						if(map[i][j]) tmp ++;//if the last number is i , it will cause tmp arguements
						if(tmp > k) break;
					}
				if(tmp > k) continue;
				for(int j = 0;j <= (k-tmp);j ++)//enumerate last status
					f[tmp+j][s] = (f[tmp+j][s]%modnum + f[j][s1]%modnum)%modnum;
			}
		}
	for(int i = 0;i <= k;i ++)//sum up the answer
		ans = (ans%modnum + f[i][tot]%modnum)%modnum;
	printf("%lld",(ans%modnum));
	return 0;
}

本文链接http://www.taodudu.cc/news/show-1782008.html