时间戳

首页 > 技术文章 > 状压dp题解

状压dp题解

hbhszxyb 2020-04-16 07:32 原文

数位dp题解：

A. 特殊方格棋盘

  • 题意：在\(n\times n\)的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。注意：同一行或同一列只能有一个车，否则会相互攻击。

  • 分析：

    • 首先，每一行只能有一个车，只要一行行地放，每行只放一个，保证同一行之间不会有攻击。
    • 其次，每一列只能放一个车，只要能记录下哪一列有车，下次不再考虑这一列就可以了。
    • 用一个二进制数S来表示某一列是否已经放置了车。例如n=5, S=01101，就表示第一、三、四列（从低位开始）已经放置了车。我们最终求出状态S=11111时的方案数。
    • 定义f[s]表示在状态s下的方案数。\(s\in [0\sim 2^n-1]\)
      • 假设 s=01101，显然有：f[01101]= f[01100]+f[01001]+f[00101]
      • 但如果在当前位置有障碍呢？所以我们再放置车的时候判断当前位是否有障碍。具体实现见代码。

  • 代码实现：

    #include<bits/stdc++.h>
const int maxn=(1<<20)-1;
typedef long long LL;
LL f[maxn],a[25];//a[x]记录第x行的障碍状态
int lowbit(int x){return x & -x;};
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;scanf("%d%d",&x,&y);
        a[x]+=1<<(y-1);
    }
    f[0]=1;//一个也不放也是一种方案
    int maxs=1<<n;//最大的状态
    for(int S=1;S<maxs;++S){//从状态1开始枚举
        int cnt=0;//计算状态S里的1的个数,几个1说明处理到第几行
        for(int i=S;i;i-=lowbit(i))cnt++;
        for(int i=S;i;i-=lowbit(i)){//依次判断当前状态每一个1
            if(!(a[cnt] & lowbit(i))){//状态S当前的1所在列如果没有障碍
                int s=S^lowbit(i);//说明lowbit(i)处可以放车，当前就在此处放车
                f[S]+=f[s];//s<S，保证能转移
            }
        }
    }
    printf("%lld\n",f[maxs-1]);
    return 0;
}

B. 互不侵犯

  • 题意：在\(n\times n\) 的棋盘里面放 n个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 个格子。
  • 分析：
    • 此题和我们讲的例题玉米地很相似，少了障碍，但多了个数限制，一般情况多一个限制我们就增加一维的状态。
    • 设dp[ i ][ j ][ k ] 为第i 行摆放国王状态为 j ，棋盘上国王数目为k的方案数.
    • 阶段很明显，就是我们可以一行一行的处理，第一行比较特殊，我们可以预处理
    • 判断冲突：假设s为当前行，s' 为上一行。
      • 行冲突，即不能相邻，只需判断 (s & (s<<1))==0，不为零说明有相邻。
      • 列冲突：
        • 上下冲突：判断(s & s')==0 ，如果不为0，说明上下冲突。
        • 左上冲突：判断((s<<1) & s')==0，如果不为0，说明冲突。
        • 右上冲突：判断((s>>1) & s')==0，如果不为0，说明冲突。
      • 判断当前状态下状态的1的个数，用lowbit即可。

D. 旅游景点

  • 题意：n个城市1~n编号，m条道路组成的连通图，要从1到n最短路，但必须经过编号为2~k+1的 k 个城市，这k个城市间，到达某些城市并停留前，必须到达其先到城市，这个地方比较绕，仔细读题意。
  • 分析：
    • 此题就是在最短路的基础上加了路径的限制和先后的限制，k<=20，我们很容易想到用 \(0\sim 2^k -1\) 的状态去枚举路径上到达城市的情况。
    • 如何解决先停留城市呢？题目里明确你可以先到后到城市再到先到城市，只要你不停留，实际上这句话的意思是让你忽略中间城市，只需要保证经过先到城市后必须经过后到城市即可。这样，我们可以先预处理出1~k+1个城市间的最短距离，并任意两城市间均为直接距离，剩下的只要处理冲突和限制即可。
    • 定义：f[s][i]，表示经过的并停留的k个城市状态为s，目前到达了城市i的最短距离。
    • 动态转移方程：\(f[s][i]=min(f[s][i],f[s'][j]+dis[j][i])\ (a[i]==s \& a[i])\)
      • \(a[i]\)记录的是在\(i\)停留之前必须到达的城市
      • 必须满足：\(s' \in s\)
#include<bits/stdc++.h>
#define pa pair<int,int>
#define inf 1000000000
using namespace std;
const int maxn=2e4+5,maxk=20+2;//1表示起点，0表示终点即n 
int n,m,K,len,ed;
int a[maxk];
int dis[maxk][maxk],d[maxn],head[maxn];
int f[1<<20][maxk];
bool vis[maxn];
struct data{int to,next,dis;}e[400005];
void Insert(int u,int v,int w){
	e[++len].to=v;e[len].dis=w;e[len].next=head[u];head[u]=len;
}
void dijkstra(int x){
	priority_queue<pa,vector<pa>,greater<pa> >q;
    for(int i=1;i<=n;i++){d[i]=inf;vis[i]=0;}
	d[x]=0;q.push(make_pair(0,x));
	while(!q.empty()){
		int now=q.top().second;q.pop();
		if(vis[now])continue;vis[now]=1;
		for(int i=head[now];i;i=e[i].next)
			if(d[now]+e[i].dis<d[e[i].to]){
				d[e[i].to]=d[now]+e[i].dis;
				q.push(make_pair(d[e[i].to],e[i].to));
			}
	}
	for(int i=1;i<=K+1;i++)
		dis[x][i]=d[i];
	dis[x][0]=d[n];//dis[x][0]来记录x到n的最短距离 
}
void dp(){
	for(int now=0;now<=ed;now++)//当前状态 
		for(int x=1;x<=K+1;x++)//当前状态下最后到达x 
			if(f[now][x]!=-1)//如果此状态未求出无法推导下一个状态 
				for(int i=2;i<=K+1;i++){//枚举下一个到达的城市i 
					int to=(now|(1<<(i-2)));//下一个状态 
					if((now&a[i])==a[i])//当前状态下必须包含下一个到达城市的先到城市 
						if(f[to][i]>f[now][x]+dis[x][i]||f[to][i]==-1)
							f[to][i]=f[now][x]+dis[x][i];
				}
}
int main(){
	scanf("%d%d%d",&n,&m,&K);
	ed=(1<<K)-1;//最终状态 
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		Insert(u,v,w);Insert(v,u,w);
	}//求出1~k+1到其他城市的最短路，即把间接变直接，且为最短 
	for(int i=1;i<=K+1;i++)dijkstra(i);
	int x;scanf("%d",&x); 
	for(int i=1;i<=x;i++){
		int u,v;scanf("%d%d",&u,&v);
		a[v]+=1<<(u-2);//把2~k+1平移一位，变成1~k 
	}
	memset(f,-1,sizeof(f));//因为距离可能为0，初始化为-1 
	f[0][1]=0;//状态0，到达城市1的最短距离为0，起点到自己 
	dp();
	int ans=inf;
	for(int i=1;i<=K+1;i++)//dis[i][0]表示i到n的最短路 
		if(f[ed][i]!=-1)ans=min(ans,f[ed][i]+dis[i][0]);
	printf("%d",ans);
	return 0;
}

推荐阅读