状压DP

糖果

原题 ：4.糖果 - 蓝桥云课 (lanqiao.cn)

给n包糖果，共有m种糖果，每包糖果包含k种不同的糖果。现在给出每包糖果的组合，求最少买多少包糖果得到 所有类别的糖果。

设dp[i]为 01状态 i （1表示有，0表示无）下，所需购买的最少糖果包数量。

状态转移方程为： \[ dp[i\space|\space a[i]] = min(dp[i \space|\space a[i]], dp[i] + 1) \] 和01背包很像，就是从 拿 和 不拿 两种状态转移过来。

这里的a[i]表示某一包糖果中包含糖果的种类，也用01串表示。

cin>>n>>m>>k;
for(int i = 1 ; i <= n ; i ++){
    for(int j = 1 ; j <= k ; j ++){
        int t;cin>>t;
        a[i] = a[i]|(1<<(t-1));
    }
}
memset(dp, inf, sizeof(dp));
dp[0] = 0;
for(int i = 1 ; i <= n ; i ++){
    for(int j = 0 ; j <= (1<<m)-1 ; j ++){
        dp[j|a[i]] = min(dp[j|a[i]], dp[j]+1);
    }
}
cout<<(dp[(1<<m)-1] == inf ? -1:dp[(1<<m)-1]);

互不侵犯

SCOI2005 互不侵犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给 NxN 个格子，放置K个国王，每个国王可以攻击到自己周围的8个格子，求国王之间互相无法攻击的总方案数。

dp{i, j, s} 表示 到第 i 行，第i行的状态为sit[j], 包括第i行在内共放了s个皇帝。

状态转移方程： \[ dp[i][j][s] = \sum \sum dp[i-1][k][s-tol[j]] \] 枚举当前状态i，上一行状态k 和 总数量s，判断合法后，转移过来。

dfs初始化

// sit -> 第i个行状态
// tol -> 第i个行状态下的数量
void dfs(int s, int sum, int x){
	if(x > n){
		sit[++cnt] = s;
		tol[cnt] = sum;
		return;
	}
	dfs(s,sum,x+1);
	dfs(s|(1<<(x-1)),sum+1,x+2);
}

检查

bool check(int a, int b){
	if(sit[a] & sit[b]) return false;
	if((sit[a]<<1) & sit[b]) return false;
	if((sit[b]<<1) & sit[a]) return false;
	return true;
}

主函数

cin>>n>>k;
dfs(0,0,1);
for(int i = 1 ; i <= cnt ; i ++){
    dp[1][i][tol[i]] = 1;
}
for(int i = 2 ; i <= n ; i ++){
    for(int j = 1 ; j <= cnt ; j ++){
        for(int r = 1 ; r <= cnt ; r ++){
            if(!check(j, r)) continue;
            for(int s = k ; s >= tol[j] ; s--){
                dp[i][j][s] += dp[i-1][r][s-tol[j]];
            }
        }
    }
}
for(int i = 1 ; i <= cnt ; i ++){
    ans += dp[n][i][k];
}
cout<<ans;

最短哈密顿回路（TSP）

P1171 售货员的难题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

位运算基础

//集合 s 代表当前集合
//右数 k 位二进制数 0/1 代表 第 k 号元素 不在集合 / 在集合 里 

//必备操作1： 
//将第k个元素加入集合
s | (1 << (k - 1));

//必备操作2：
//将第k个元素从集合中删除
s & (~ (1 << (k - 1)) );

//必备操作3：
//1)如果第k个元素在 集合s里， 删除它
//2)如果不在，把它加入集合s
//可以想象成一盏灯的开关:
//按下开关， 明 -> 暗， 暗 -> 明 
s ^ (1 << (k - 1));

//必备操作4:
//判断元素k 是否在集合s里
//在：返回1，不在：返回0 
(s >> (k - 1)) & 1 == 1

dp{S, V}中S表示经过的点，V表示当前S中的最后一个点。

首先，枚举每个状态S，取S中未到达的点V，和S中已经到达的点U，更新dp{S，V}

最后，再利用DP[（1<<n） - 1] [V] , 判断最后回到起点的最短距离

#include<bits/stdc++.h>
using namespace std;
const int MAX = (1<<20);
const int INF = 0x3f3f3f3f;

int n,ans;
int dp[MAX][21],e[21][21];

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			cin>>e[i][j];
		}
	}
	memset(dp,INF,sizeof(dp));
	dp[1][1] = 0;
	//状态 （s，v）；
	//下一步的点 u
	for(int s = 0 ; s <= (1<<n) - 1 ; s ++){
		for(int u = 1 ; u <= n ; u ++){
			if( !( s & (1 << u-1) )){
				for(int v = 1 ; v <= n ; v ++){
					if( s & (1 << v-1) ){
						dp[s| (1 << u-1) ][u] = min(dp[s | (1 << u-1)][u], 
                                                    dp[s][v] + e[v][u]);
					}
				}
			}
		}
	}
	ans = INF;
	for(int i = 2 ; i <= n ; i ++){
		ans = min(dp[(1<<n)-1][i] + e[i][1], ans);
	}
	cout<<ans;
	return 0;
}