状压DP学习笔记

发布于 2019-09-14  191 次阅读


动态规划的过程是随着“阶段”的增长,在每个状态维度上不断拓展的。在任意时刻,已经求出最优解的状态与尚未求出最优解的状态在各维度上的分界点组成了DP拓展的“轮廓”。对于某些问题,我们需要在动态规划的“状态”中记录一个集合,保存这个“轮廓”的详细信息,以便进行状态转移。若集合大小不超过N,集合中每个元素都是小于K的自然数,则我们可以把这个集合看作一个N位K进制数,以一个$latex [0,K^N-1]$之间的十进制整数的形式作为DP状态的一维。

这种把集合转化为整数记录在DP状态中的一类算法,被称为 状态压缩动态规划

经典例题

旅行商问题

题目地址

可以将这道题这么理解:

平面设计有n个点,每个点的坐标是(xi,yi),问从一号点走完所有点最后再回到一号点的最短路径。

首先每个点没有必要走两次,走一次就够了。

变化量:

1.当前在哪个点;

2.走过哪些点(我们需要从没走过的点里面选一个走);

状态设置:f[s][i]表示我现在走到了第i个点,走过了哪些点(s);

但是走过哪些点怎么用一个整数表示?

我们就要用到了状态压缩:把一个数组压缩成一个数。

假设我们有五个点:

img

情况是:我们已经走了1,2,4 这三个结点了,3,5结点还没有走:

img

我们将走过的结点的位置写上1,未走过的结点的位置写上0:

img

我们可以将下面这个01串看做是一个二进制的数,然后我们再将其转化成十进制的数:

img

这样的话,我们就将这种情况转化成了一个数字,这就是状态压缩。

边界条件:

f[1][0]=0,我只走了第0个点(1只有第0位有1),当前位置在0,时间是0;

状态转移方程:

我们找个没走过的点走一下就好了。

枚举一个j,看看 s 的二进制的第 j 位是不是 0 ,如果是 0 就走 j ,并把第 j 位改成 1;

注意要先枚举状态在枚举每个点,因为我们走的点是越来越多的。

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<map>
#define N 500010
#define INF 0x3f3f3f3f
#define pi 3.1415926535897932384626433

using namespace std;

int _map[50][50];
int f[N][20];

int main()
{
	int t;
	cin>>t;
	while (t--)
	{
		memset(_map,0x3f,sizeof(_map));
		int n,m;
		cin>>n>>m;
		for (int i=1;i<=m;i++)
		{
			int x,y,val;
			cin>>x>>y>>val;
			if (_map[x-1][y-1]>val) _map[x-1][y-1]=_map[y-1][x-1]=val;
		}
		for (int i=0;i<n;i++)
			_map[i][i]=0;
		for (int k=0;k<n;k++)
			for (int i=0;i<n;i++)
				for (int j=0;j<n;j++)
					_map[i][j]=min(_map[i][j],_map[i][k]+_map[k][j]);//floyd求最小值
		memset(f,0x3f,sizeof(f));
		f[1][0]=0;
		for (int s=0;s<(1<<n);s++)	//枚举每种状态
			for (int i=0;i<n;i++)	//枚举当前结点是哪个数
				if (f[s][i]<INF)
				{
					for (int j=0;j<n;j++)//枚举哪个数没去过
						if (((s>>j) & 1)==0)//如果s的第j位是0,说明没去过
						{
							int news=s | (1<<j);//新的状态:将s的第j位变成1
							f[news][j]=min(f[news][j],f[s][i]+_map[i][j]);//更新
						}
				}
		int ans=INF;
		for (int i=0;i<n;i++)
			ans=min(ans,f[(1<<n)-1][i]+_map[i][0]);//枚举每个终点,然后记得要返回0号结点
		cout<<ans<<endl;
	}
	return 0;
}

例二:

题目地址

在一个种草之后,与之相邻的四个格子都不能种草了;

状态定义:f[i][s] 表示前 i 行的草已经种完了,且第 i 行种的草的长相是 s;

状态转移方程:

前 i 行已经种完草了,我们考虑第 i+1 行怎么种草;

第 i+1 行不能连着种草。所以用二进制表示的时候不能有两个连续的两个1,由于相邻的两列也不能种草,所以第 i 行种草的地方第 i+1 行不能种草。

假设我们第二行的种植情况是这样的:

img

由于相邻的格子不能种植,所以我们可以确定第 i+1 行一定不能种在这些格子上:

img

其他的位置问你不能确定,但是我们可以发现一个规律:si & si+1 = 0。

所以我们只要先找一个s',使得 s & s' = 0 就行了。

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<map>
#define N 50010
#define INF 0x3f3f3f3f
#define pi 3.1415926535897932384626433
#define Mod 100000000

using namespace std;

int f[20][N];
int _map[50][50];
int a[50];
int g[N];

int main()
{
	int m,n;
	cin>>m>>n;
	for (int i=1;i<=m;i++)
		for (int j=1;j<=n;j++)
		{
			cin>>_map[i][j];
			a[i]=(a[i]<<1)+_map[i][j];
		}
	for (int s=0;s<(1<<n);s++)
		g[s]=(!(s & (s<<1))) && (!(s & (s>>1)));
	f[0][0]=1;
	for (int i=1;i<=m;i++)
	{
		for (int s=0;s<(1<<n);s++)
		{
			if (g[s] && ((s & a[i])==s))
			{
				for (int t=0;t<(1<<n);t++)
					if ((s&t)==0)
						f[i][s]=(f[i][s]+f[i-1][t])%Mod;
			}
		}
	}
	int ans=0;
	for (int i=0;i<(1<<n);i++)
		ans=(ans+f[m][i])%Mod;
	cout<<ans<<endl;
	return 0;
}

例三

题目地址

发现和上一个题没有什么本质的区别,只是多了个条件确定个数的国王;

题目多一个条件直接多加一个维度:

状态定义:f [i][s][j] 第 i 行的国王已经放完了,已经放了 j 个国王的情况下,第 i 行国王放置的情况为 s;

相比于上个题来说只是再需要判断一下对角线上也不能放国王就好了。

还不如打表

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<map>
#define N 100010
#define INF 0x3f3f3f3f
#define pi 3.1415926535897932384626433

using namespace std;

long long dp[15][N][15];
int a[N],num[N];
int cnt;

int getsum(int x)
{
	int sum=0;
	while (x)
	{
		sum+=x & 1;
		x>>=1;
	}
	return num[cnt]=sum;
}

int main()
{
	int n,m;
	cin>>n>>m;
	for (int i=0;i<(1<<n);i++)
		if (!(i & (i<<1))) a[++cnt]=i,dp[1][cnt][getsum(i)]=1;//预处理
	for (int i=2;i<=n;i++)
		for (int j=1;j<=cnt;j++)//枚举当前行状态,合法状态已经存储在了a[]数组中
			for (int k=1;k<=cnt;k++)//枚举前一行状态
			{
				int x=a[j],y=a[k];
				if ((x&y)||(x&(y<<1))||(x&(y>>1))) continue;
				for (int l=0;l<=m;l++) dp[i][j][num[j]+l]+=dp[i-1][k][l];//感性理解转移方程
			}
	long long ans=0;
	for (int i=1;i<=cnt;i++)
		ans+=dp[n][i][m];
	cout<<ans<<endl;
	return 0;
}x>>=1;
	}
	return num[cnt]=sum;
}

int main()
{
	int n,m;
	cin>>n>>m;
	for (int i=0;i<(1<<n);i++)
		if (!(i & (i<<1))) a[++cnt]=i,dp[1][cnt][getsum(i)]=1;//预处理
	for (int i=2;i<=n;i++)
		for (int j=1;j<=cnt;j++)//枚举当前行状态,合法状态已经存储在了a[]数组中
			for (int k=1;k<=cnt;k++)//枚举前一行状态
			{
				int x=a[j],y=a[k];
				if ((x&y)||(x&(y<<1))||(x&(y>>1))) continue;
				for (int l=0;l<=m;l++) dp[i][j][num[j]+l]+=dp[i-1][k][l];//感性理解转移方程
			}
	int ans=0;
	for (int i=1;i<=cnt;i++)
		ans+=dp[n][i][m];
	cout<<ans<<endl;
	return 0;
}

最美好的事情就是和OI一起成长呢。