Yurchiu's Blog
Yurchiu
An AFO whker.
  首页
  归档
158
  标签
81
  分类
24
  说说
  关于
  留言
  链接
  设置

一些状压 DP 题目

Yurchiu 2021-02-05, 13:10:44 3.4k 隐藏左右两栏 展示左右两栏
首页 / 一些状压 DP 题目

以下是一些状压 DP 题目，为本蒟蒻在上 luogu 网课时所整理**。题解超多**。

前置知识

  • 用数表示集合。数的二进制的第 ii 位的 01 状态可表示一个元素是否在集合中。
  • lowbit⁡(x)\operatorname{lowbit}(x) 表示数 xx 的最低的为 11 的一位。lowbit(x)=x&(-x)​。
  • 判断 xx 是不是 yy 的子集：x&y==x。
  • xx 和 yy 的交集 x&y，并集 x|y。
  • xx 是 yy 的子集时，y−xy-x：x^y。
  • 枚举 SS 的子集：for(int i=S;i;i=i-1&S)。其中 ii 是 SS 的子集。
  • 判断 ss 从右边数第 ii 位是否为 11：s&(1<<(i-1))。
  • 把 ss 从右边数第 ii 位变成 11：s|(1<<(i-1))。

P3052 [USACO12MAR]Cows in a Skyscraper G

题意

给出 nn 个物品，体积为 wiw_i，现把其分成若干组，要求每组总体积 ≤W\le W，问最小分组数。

n≤18n \le 18，$ W \le 10^8$。

点击查看题解

题解

我们用 dp[S] 表示 SS 这个集合最小分组数，vol[S]表示 SS 这个集合的总体积。初始化为极大值。

枚举 nn 个物品的子集，再枚举每个子集中的物品。

这个物品 aa 也许需要另开一个组，或利用原来的组。

另开一组：

状态转移方程是 dp[S]=min(dp[S-a]+1)，其中 aa 为 SS 中的物品。既然 SS 相对 S−aS-a 多开了一组，则 SS 集合相当于总体积清空了再加上新的物品 aa 的体积。当然，当 SS 的分组数相同时，我们希望 aa 的体积，即新开组被占体积还要尽可能小，这样才有可能装下更多物品。

利用原来的组：

条件是，原来的组的空余足够物品 aa 放入。

状态转移方程是 dp[S]=min(dp[S-a])，其中 aa 为 SS 中的物品。既然 SS 相对 S−aS-a 组数不变，则 SS 集合相当于 S−aS-a 的体积又加上新的物品 aa 的体积。同样，我们仍希望它尽可能小。

然后输出 dp[S] 即可。这里的 “S” 表示所有物品的集合。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=1<<18;
	int n,w,a[20],dp[N],vol[N];
	void yzmain()
	{
		scanf("%d%d",&n,&w);
		for(int i=0;i<n;i++) scanf("%d",a+i);
		for(int i=0;i<(1<<n);i++) vol[i]=214748367;
		for(int i=1;i<(1<<n);i++) dp[i]=214748367;
		for(int i=1;i<(1<<n);i++)
    	{
        	for(int j=0;j<n;j++)
        	if(i>>j&1) 
			{
            	if(dp[i^(1<<j)]+1<dp[i])
					dp[i]=dp[i^(1<<j)]+1,vol[i]=a[j];
				else if(dp[i^(1<<j)]+1==dp[i]&&a[j]<vol[i])
					dp[i]=dp[i^(1<<j)]+1,vol[i]=a[j];
				if(vol[i^(1<<j)]+a[j]<=w)
				{
					if(dp[i^(1<<j)]<dp[i])
						dp[i]=dp[i^(1<<j)],vol[i]=vol[i^(1<<j)]+a[j];
					else if(dp[i^(1<<j)]==dp[i]&&vol[i^(1<<j)]+a[j]<vol[i])
						dp[i]=dp[i^(1<<j)],vol[i]=vol[i^(1<<j)]+a[j];
         		}
        	}
    	}
		printf("%d",dp[(1<<n)-1]);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P2704 [NOI2001] 炮兵阵地

题意

有 n×mn \times m 的网格，一个格子可以是高原或平原。平原上可部署炮兵部队，可攻击到上下左右各两个格子。要求部队之间不能互相攻击，求可部署的最大值。

n≤100n \le 100，m≤10m \le 10。

点击查看题解

题解

我们可以按行来 dp，因为若一行一行地，只考虑前两行就可以了。

可以设 dp[i][A][B] 表示对于第 ii 行，当第 i−2i-2 行和第 i−1i-1 行放的部队的状态是 AA 和 BB 时，最多放多少部队。其中 AA 和 BB 仍可以按 01 集合的方式保存（实际上，合法的集合很少，为了防止 MLE，可以用一个编号代表一个集合）。

这样，若可转移，dp[i][A][B] 就可以转移到 dp[i+1][B][C]。其中 CC 表示第 ii 行放的部队的状态。

接下来就很简单了。详情看代码。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=105;//大概合法阵型有这些
	int n,m,set[N],cset=0,num[N],hgh[N],dp[N][N][N],ans=0;
	char g[100+5][10+5];
	void yzmain()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			cin>>g[i];
		for(int i=0;i<(1<<m);i++)//枚举阵型（二进制）
		{
			bool flag=false;//冲突
			int cnt=0;//人数
			for(int j=0;j<m;j++)
				if((i>>j)&1)//j+1处有部队
				{
					flag |= ( (i>>(j+1)&1) || (i>>(j+2)&1) ); //影响范围为2
					cnt++;
				}
			if(!flag) set[++cset]=i,num[cset]=cnt; //保存阵型、人数
		}
		for(int i=1;i<=n;i++)
			for(int j=0;j<m;j++)
				if(g[i][j]=='H') hgh[i]|=(1<<j);//存储高地集合
		
		for(int j=1;j<=cset;j++)
			for(int k=1;k<=cset;k++)
				if(!(set[j]&hgh[1]) && !(set[k]&hgh[2]) && !(set[j]&set[k]))//阵型不能和高地冲突，不能互相冲突
					dp[2][j][k]=num[j]+num[k];//预处理，用以后面的递推
		
		for(int i=3;i<=n;i++)
		for(int l=1;l<=cset;l++)
			if(!(set[l]&hgh[i]))
				for(int j=1;j<=cset;j++)
				for(int k=1;k<=cset;k++)
					if(!(set[l]&set[j]) && !(set[l]&set[k]))
						dp[i][k][l]=max(dp[i][k][l],dp[i-1][j][k]+num[l]);//很好理解
		
		for(int j=1;j<=cset;j++)
			for(int k=1;k<=cset;k++)
				ans=max(ans,dp[n][j][k]);
				
		printf("%d",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P1896 [SCOI2005]互不侵犯

题意

在 n×nn×n 的棋盘里面放 kk 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 88 个格子。

1≤n≤91\le n \le9，0≤k≤n20\le k \le n^2。

点击查看题解

题解

类似“炮兵阵地”，此处不再赘述，详情请看代码。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=15000;//大概合法阵型有这些
	long long n,m,set[N],cset=0,num[N],dp[20][N][200],ans=0;
	//dp[第i行][阵型][前面已放置数]=方案数;
	void yzmain()
	{
		scanf("%lld%lld",&n,&m);
		for(int i=0;i<(1<<n);i++)//枚举阵型（二进制）
		{
			int cnt=0,tmp=i;
			if(i&(i<<1)) continue;//影响范围：2
			while(tmp) cnt+=tmp%2,tmp/=2;
			set[++cset]=i,num[cset]=cnt; //保存阵型、人数
		}
		
		for(int i=1;i<=cset;i++)
			if(num[i]<=m)
				dp[1][i][num[i]]=1;
		
		for(int i=2;i<=n;i++)
			for(int j=1;j<=cset;j++)
				for(int k=1;k<=cset;k++)
				{
					if((set[j]&set[k])||(set[j]&(set[k]<<1))||(set[j]&(set[k]>>1))) continue;//左上，上，右上冲突
					for(int used=1;used<=m;used++)
						if(used+num[j]<=m)
							dp[i][j][used+num[j]]+=dp[i-1][k][used];
				}
		
		for(int i=1;i<=n;i++)
			for(int j=1;j<=cset;j++)
				ans+=dp[i][j][m];
				
		printf("%lld",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P1879 [USACO06NOV]Corn Fields G

题意

有 n×mn \times m 的网格，一个格子可以是高原或平原。平原（11）上可部署炮兵部队，可攻击到上下左右各一个格子。要求部队之间不能互相攻击，求可部署的方案数（不部署算一种）。这本来不是一个奶牛题吗？

点击查看题解

题解

做法类似”炮兵阵地“。以下代码用了一种记忆化搜索的形式求解。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
    const long long M=1<<15,N=20,Mod=100000000,Num=0;
    long long n,m,cset=0;
    long long set[N][M],b[M],nset[M],hgh[M],dp[N][M];
    char g[100+5][10+5];
    long long dfs(long long step,long long s)
    {
    	long long ret=0;
    	if(step==n) return dp[step][s]=1;
    	if(dp[step][s]) return dp[step][s];
		for(long long i=1;i<=set[step+1][Num];i++)
		{
			if(s&set[step+1][i]) continue;
			ret=(ret+dfs(step+1,set[step+1][i]))%Mod;
		}
		return dp[step][s]=ret;
	}
    void yzmain()
    {
    	long long tmp;
        scanf("%lld%lld",&n,&m);
        for(long long i=1;i<=n;i++)
            for(long long j=1;j<=m;j++)
            	scanf("%lld",&tmp),hgh[i]=hgh[i]*2+tmp;
        for(long long i=0;i<(1<<m);i++)
        {
            if(i&(i<<1)) continue;
			nset[++nset[Num]]=i;
        }
        for(long long i=1;i<=n;i++)
        {
        	memset(b,0,sizeof(b));
        	for(long long j=1;j<=nset[Num];j++)
        	{
        		long long now=nset[j]&hgh[i];
        		if(b[now]) continue;b[now]=1;
        		set[i][++set[i][Num]]=now;
			}
		}
        printf("%lld",dfs(0,0)%Mod);
        return;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    _yz::yzmain();
    return 0;
}

P4011 孤岛营救问题

题意

n×mn\times m 的网格，(1,1)(1,1) 入，(n,m)(n,m) 出，上下左右可移动。网格间有门和墙（<150<150），一些网格内有钥匙，若有相应钥匙门可通过，墙不可通过。问最小步数。 钥匙和门的种类不超过 1414。nn，mm 不超过 1010。

点击查看题解

题解

求最小步数，使用 bfs。若处于同一个网格，且手里的钥匙不同，视为不同状态。由于钥匙可以用多次，对已经获取的钥匙状态压缩。搜索的状态总数为 n×m×2nn\times m \times 2^n，每个状态只会访问一次。

注意，一个房间内可能有多个钥匙。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=15,xpos[]={0,0,0,1,-1},ypos[]={0,1,-1,0,0},Inf=999999999;
	int g[N*N][N*N],v[N*N][1<<N],key[N*N],n,m,p,k,s,ans=Inf;
	struct Status{int pos,st,step;}status;
	queue<Status>q; 
	int enc(int x,int y){return x*11+y;}
	void dec(int &x,int &y,int data){x=data/11;y=data%11;}
	void bfs()
	{
		q.push((Status){enc(1,1),0,0});
		v[enc(1,1)][0]=1;
		while(!q.empty())
		{
			Status now=q.front();q.pop();
			int nx,ny;dec(nx,ny,now.pos);
			if(nx==n && ny==m) ans=min(ans,now.step);
			now.st|=key[now.pos];
			v[now.pos][now.st]=1;
			for(int i=1;i<=4;i++)
			{
				int tx=nx+xpos[i],ty=ny+ypos[i];
				int to=enc(tx,ty);
				if(v[to][now.st]) continue;
				if(tx>n || tx<1 || ty>m || ty<1) continue;
				if(g[now.pos][to]==-1) q.push((Status){to,now.st,now.step+1});
				else if(g[now.pos][to]>=1 && (now.st&(1<<(g[now.pos][to]-1)))) q.push((Status){to,now.st,now.step+1});
			}
		}
		return;
	}
	void yzmain()
	{
		int t1,t2,t3,t4;
		scanf("%d%d%d%d",&n,&m,&p,&k);
		memset(g,-1,sizeof(g));
		for(int i=1;i<=k;i++)
			scanf("%d%d%d%d",&t1,&t2,&t3,&t4),
			scanf("%d",&g[enc(t1,t2)][enc(t3,t4)]),
			g[enc(t3,t4)][enc(t1,t2)]=g[enc(t1,t2)][enc(t3,t4)];
		scanf("%d",&s);
		for(int i=1;i<=s;i++)
			scanf("%d%d%d",&t1,&t2,&t3),
			key[enc(t1,t2)]|=1<<(t3-1);
		bfs();
		printf("%d",ans==Inf?-1:ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P1433 吃奶酪

题意

房间里放着 nn 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0)(0,0) 点处。

点击查看题解

题解

以前暴搜 dfs + 玄学（最优化）剪枝是可以过的，不过现在数据得到加强（也变绿了.jpg），要用状压 dp 了。

设 f[v][s] 为已经访问了 ss 的点集，目前正在 vv 点，访问剩下的点需要的最小路径长度。所以 f[0][0] 就是题目所求。

这样我们通常可以得到一个 n2×2nn^2\times 2^n 的算法。在 n<20n<20 的情况下比 n!n! 要好很多。这就是竞赛中在 nn 较小的情况下进行状压 dp 的原因。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=16;
	struct Pos{double x,y;}p[N];
	int n,end;
	double f[N][1<<N],d[N][N];
	double dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
	double dfs(int now,int st)
	{
		if(f[now][st]>=0) return f[now][st];
		if(st==end) return f[now][st]=0;
		f[now][st]=999999999;
		for(int i=1;i<=n;i++)
		{
			if(st&(1<<(i-1))) continue;
			f[now][st]=min(dfs(i,st|(1<<(i-1)))+d[now][i],f[now][st]);
		}
		return f[now][st];
	}
	void yzmain()
	{
		scanf("%d",&n);end=(1<<n)-1;
		for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				d[i][j]=dis(p[i].x,p[i].y,p[j].x,p[j].y);
		for(int i=0;i<=n;i++)
			for(int j=0;j<=end;j++)
				f[i][j]=-1;
		printf("%.2lf",dfs(0,0));
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}



本文作者：Yurchiu

本文链接：https://yz-hs.github.io/e026536f428a/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。


OI 动态规划 一些 状压 DP
最后更新：2023-08-21, 23:18:21
By Yurchiu.
最近更新旧文更新
[Works] 自白 终章
《幽默报 10》
AFO 有感
OI 之旅
《幽默报》
[Works] 自白
[Idea] 试卷排序
其他物件杂物收纳
Hitokoto

Yurchiu 说，除了她以外的人都很强！嘤嘤嘤~~
博客信息
文章数目
158
最近更新
08-21
本站字数
350.6k
文章目录

©2019-2023 Yurchiu. All rights reserved.

Theme Cutie, by Yurchiu.