#创作计划#教你食用状压DP

key0213

2024-11-04 14:01:37

发布于：福建

189阅读

0回复

0点赞

在被Macw的排位赛#13第7题拿捏后，我不得不去烹调一波状压DP，现做出此文，教大家食用状压DP。
~~这是个好东西，学会了可以做好多绿题和蓝题~~
阅读此文前，你需要自学DP、进制数以及位运算的基本知识等。
好，进入正文！

No.1 前置知识

‌状压DP（状态压缩动态规划）是一种特殊的动态规划方法，它将状态压缩为二进制整数来表示，以便更有效地进行状态转移和优化。‌

好！看完后，我们知道，状压DP=状压（‌状态压缩）+DP（动态规划）；
DP就先不介绍了，接下来让我们先谈谈状态压缩。

No.2 状态压缩

‌状态压缩是一种将“物品”状态通过 $n$ 进制数表示的技巧（ $n$ 为状态数, 一般较小，通常为 $2$ ）。通常用一个整数其 $n$ 进制中的第 $i$ 位上的数来表示第 $i$ 个“物品”的状态‌，状态压缩的核心在于使用位运算来处理和比较。

比如：二进制可以用于表示棋盘上一行的格子是否有棋子（有无，共 $2$ 种）、硬币的正反面（正反，共 $2$ 种）、该物品取不取（是否取，共 $2$ 种）等。
比如我们有一行 $8$ 个方格，在方格里填充 $0$ 和 $1$ ，那么总的方案数就应该有 $2^8$ 个。我们现在使用状态压缩，将 $8$ 个方格看成 $8$ 位， $0$ 和 $1$ 都看成二进制，那么这 $8$ 位就组成了一个二进制数。比如0001 0010转成十进制就是 $18$ ，它表示从右往左第 $2$ 和第 $5$ 个方格里是 $1$ 。

例题1：充满希望的拼接质数1

我们假设 $n$ 为 $4$ ，考虑一个状态 $x$ ，这个 $x$ 的二进制取值范围在0001~1111之间，二进制从右往左第 $i$ 位为 $1$ 表示取第 $i$ 块水晶；
那么我们可以枚举 $1$ ~ $(2^4-1)$ 的区间，即枚举二进制0001~1111这个区间里的所有状态，然后求出状态 $x$ 中取的水晶之和，最后判断质数即可。

#include<bits/stdc++.h>
using namespace std;
int n,a[20],ans;
int check(int x){//判断质数
    if(x<=1) return 0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<(1<<n);i++){//枚举所有状态 1<<n -> 2^n
        int sum=0; 
        for(int j=0;j<n;j++){
            if(i&(1<<j)){//判断第j位是否为1
                sum+=a[j];//求和
            }
        }
        if(check(sum)) ans++;//如果为质数，答案加1
    }
    cout<<ans;
    return 0;
}

例题2：披萨店

和上题差不多，我们输入时可以用一个 $vector$ 存储会产生冲突的披萨，仍然枚举所有状态，判断一个状态中会不会产生冲突，否则答案加 $1$ ，具体看代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[20],ans;
vector<int>e[20];//e[i]存储会和i号披萨冲突的披萨
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        e[a-1].push_back(b-1);//存储冲突，下标减一是为了下面的判断
        e[b-1].push_back(a-1);
    }
    for(int i=0;i<(1<<n);i++){//枚举状态
        int f=0;//f=1 状态i不成立;f=0 状态i成立
        for(int j=0;j<n;j++){
            if(i&(1<<j)){//判断是否选了j号披萨
                for(int k=0;k<e[j].size();k++){
                    if(i&(1<<(e[j][k]))){//判断和j号披萨冲突的披萨有没有选
                        f=1;
                        break;
                    }
                }
                if(f) break;
            }
        }
        if(!f) ans++;//如果状态是成立的，答案加1
    }
    cout<<ans;
    return 0;
}

No.3 位运算的小技巧

为了方便接下来的理解，我们先来学习些位运算的小技巧：

代码	作用
`n&1`	判断n是否为奇数
`n&m`	判断n和m二进制中是否有同为一的位置
`n&(n-1)`	消去n二进制中最右侧的1
`n>0&&(n&(n-1))==0`	检查n是否为2的幂次方
`n&(-n)`	n的最右边一个1的位置对应的数
`n&(1<<(i-1))`或`n>>(i-1)&1`	判断n的第i位是否为1（输入时从1开始）
`n&(~(1<<(i-1)))`	去掉n的第i位的1（输入时从1开始）
`n^(1<<(i-1))`	将n的第i位取反
`n or (1<<(i-1))`	将n第i位变为1
$······$	$······$

例题1：高低位交换
我们可以用x<<16让 $x$ 的后 $16$ 位移到前面去，原来的前 $16$ 位会溢出；
我们可以用x>>16让 $x$ 的前 $16$ 位移到后面去，原来的后 $16$ 位会溢出；
两个相加即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unsigned int n;//32位整数才可以满足（满足让16位溢出，一共只有32位，int和long long不行）
int main(){
    cin>>n;
    cout<<(n<<16)+(n>>16);//两个相加完成高低位交换
    return 0;
}

No.4 状压DP

接下来我们回到状压DP。
状压DP：顾名思义，就是用状态压缩实现DP；
状压DP主要分为棋盘式和集合式：

棋盘式：主要用于处理棋盘类问题，通过状态压缩来表示棋盘上每个格子的状态（如是否有障碍物、是否被占用等）。这种方法常用于解决如迷宫问题、棋盘游戏等问题‌；
集合式：用于表示一个集合中的元素是否被选择。这种方法适用于处理如背包问题、选择问题等，通过二进制数来表示集合中的元素状态，每个二进制位对应集合中的一个元素，1表示选择该元素，0表示不选择‌。

4.1 棋盘式：

例题1：[SCOI2005] 互不侵犯
首先，我们根据之前的经验，考虑枚举一行的所有状态，即从 $0$ ~ $(2^N-1)$ 枚举一遍，判断合法的状态，用一个数组存下来，并存储 $i$ 状态中放的国王数量；
那，怎么判断合法呢？怎么算放的国王数量呢？这就要用到上文说的一些技巧了：

//算放的国王数量
ll check(int x){//统计一个数二进制中一的个数
	ll sum=0;
	while(x){
		sum++;//每消去一个1，sum++
		x&=(x-1);//上表中的：消去二进制中最右侧的1
	}
	return sum;
}
//--------------------------
//当前行状态i ，上一行状态j
//判断上下行合法 ：
// i&j ->为1：两行中有位置都放了国王（不成立）
//例：
//j：01001
//i：01010
//i&j:01000 当前状态中从右往左第4个位置上下行都有国王
//判断当前行合法 ：
// i&(j<<1) ->为1：当前行中有些国王右上角也有国王（不成立）
//例：
//j：01100
//j<<1：11000
//i：10010
//i&(j<<1):10000 当前状态中从右往左第5个国王的右上角也有个国王
// i&(j>>1) ->为1：当前行中有些国王左上角也有国王（不成立）
//例：
//j：01100
//j>>1：00110
//i：10010
//i&(j<<1):00010 当前状态中从右往左第2个国王的左上角也有个国王
//i&(i<<1) ->为1：当前行中有些国王旁边也有国王（不成立）
//例：
//i：01101
//i<<1：11010
//i&(i<<1)：01000 当前状态中从右往左第4个国王的右边也有个国王

这样就可以预处理所有的状态了：

for(int i=0;i<(1<<n);i++){//枚举所有状态
	if(i&(i<<1)) continue;//不合法则跳过
	f[++L]=i;//保存合法的状态
	cnt[L]=check(i);//记录每个状态放的国王数量（check函数见上文） L 表示合法的状态总数
	dp[1][L][cnt[L]]=1;//dp数组初始化（详见下文）
}

接下来，我们考虑DP：

状态： $dp[i][j][k]$ 表示第 $i$ 行状态为 $j$ ，当前共放了 $k$ 个国王的方案数；
转移方程：由于当前状态可以由上一行所有不会产生冲突的状态转移而来，所以状态转移方程为

$dp[i][j][l]=\sum_{i=1}^{L} dp[i-1][l][g-cnt[j]]$

其中， $i$ 表示当前第 $i$ 行， $j$ 表示当前状态， $l$ 表示上一状态， $g$ 表示当前放的国王总数， $L$ 和 $cnt$ 数组见上文；
3. 初始条件：由于 $dp$ 数组需要由上一行得到，所以我们需要初始化 $dp$ 数组的第一行，而 $dp$ 数组第一行的方案即所有合法的状态，所以在枚举合法方案时初始化即可，dp[1][L][cnt[L]]=1;；
4. 循环顺序：我们第一层循环 $i$ ，表示第 $i$ 层，第二层循环 $j$ ，枚举当前状态，第三层循环 $l$ ，枚举上一行状态，如果状态 $j$ 和状态 $l$ 不会产生冲突，那么循环 $g$ ，从 $cnt[j]$ （至少有当前状态放的国王数量）到 $k$ （数量上限），枚举当前放的国王总数；
5. 显而易见，答案是 $dp$ 数组中第 $n$ 行放 $k$ 个国王的所有状态的方案之和，即

$\sum_{i=1}^{L} dp[n][i][k]$

那么DP自然就出来了

for(int i=2;i<=n;i++){//从第2行开始
	for(int j=1;j<=L;j++){//枚举当前行所有状态
		for(int l=1;l<=L;l++){//枚举上一行所有状态
			if(f[j]&f[l]||f[j]&(f[l]<<1)||f[j]&(f[l]>>1)) continue;//两行会冲突则跳过
			for(int g=cnt[j];g<=k;g++){//枚举国王数
				dp[i][j][g]+=dp[i-1][l][g-cnt[j]];//状态转移方程
			}
		}
	}
}

最后贴一波代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
ll n,k,dp[15][2005][105],cnt[2005],f[2005],L;
ll check(int x){//求一个状态的国王数
	ll sum=0;
	while(x){
		sum++;
		x&=(x-1);
	}
	return sum;
}
int main(){
	cin>>n>>k;
	for(int i=0;i<(1<<n);i++){//枚举所有状态
		if(i&(i<<1)) continue;
		f[++L]=i;
		cnt[L]=check(i);
		dp[1][L][cnt[L]]=1;//初始化
	}
	for(int i=2;i<=n;i++){//DP过程
		for(int j=1;j<=L;j++){
			for(int l=1;l<=L;l++){
				if(f[j]&f[l]||f[j]&(f[l]<<1)||f[j]&(f[l]>>1)) continue;
				for(int g=cnt[j];g<=k;g++){
					dp[i][j][g]+=dp[i-1][l][g-cnt[j]];//状态转移方程
				}
			}

		}
	}
	ll ans=0;
	for(int i=1;i<=L;i++){//答案
		ans+=dp[n][i][k];
	}
	cout<<ans;
	return 0;
}

例题2：
[USACO06NOV] Corn Fields G
Acwing.玉米田
 乌龟养殖场
额，好好好，这么玩是吧（~~我赛时咋没发现~~），这几题差不多（差别在有的可以一个都不放），所以这里具体就讲 $[USACO06NOV] Corn Fields G$ 这题。
这一题和上一题差不多，但少了个数限制，且冲突条件变了。
所以我们先来想想如何存图。这一题里，图显然只会在判断第 $i$ 行状态是否有在不适合种草地方种草，怎么判断呢？如果把牧场第 $i$ 行的土地状况存储为一个状态 $mp[i]$ ，当前状态为 $j$ ，我们可以用(~mp[i])&j来判断。为什么？~mp[i]会把第 $i$ 行不适合种草的地方标记为 $1$ ，肥沃的反标记为 $0$ ，而(~mp[i])&j有值则说明~mp[i]中有些 $1$ 的位置状态 $j$ 中也为 $1$ ，即在不适合种草的地方种了草，所以不成立。那既然会用到~mp[i]，那么我们输入时就可以把 $mp$ 数组取反，这样就不用后面取反了。
那这样就可以存图了：

cin>>n>>m;
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		int x;
		cin>>x;//读入地图
		mp[i]=(mp[i]<<1)+!x;//取反存储
	}
}

接下来为了存储所有合法状态，我们来想想怎样判断状态合法。
有了上题的经验，当前状态若为 $i$ ，那么i&(i<<1)有值则说明当前状态中有连续的 $1$ ，即有些种草的地旁边也有草，不成立；
上行状态为 $j$ ，若i&j有值则说明两行中有位置都是 $1$ ，即都种了草，不成立。
存储所有合法状态时用i&(i<<1)判断就可以了：

for(int i=0;i<(1<<m);i++){//枚举所有状态，因为都不放也可以，所有从0开始
	if(i&(i<<1)) continue;//不成立跳过
	zt[++L]=i;////保存合法的状态 L 表示合法的状态总数
}

我们接下来再考虑DP：

状态： $dp[i][j]$ 表示第 $i$ 行状态为 $j$ 的方案数；
转移方程：由于当前状态可以由上一行所有不会产生冲突的状态转移而来，所以状态转移方程为

$dp[i][j]=dp[i-1][k]$

其中， $i$ 表示当前第 $i$ 行， $j$ 表示当前状态， $k$ 表示上一状态；
3. 初始条件：由于 $dp$ 数组需要由上一行得到，所以我们也可以初始化第0行放一个的情况：dp[0][1]=1;；
4. 循环顺序：我们第一层循环 $i$ ，表示第 $i$ 层，第二层循环 $j$ ，枚举当前状态，第三层循环 $k$ ，枚举上一行状态即可；
5. 显而易见，答案是 $dp$ 数组中第 $n$ 行放 $k$ 个国王的所有状态的方案之和，即

$ANS=\sum_{i=1}^{L} dp[n][i]$

最后放一下代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll P=1e8;
int n,m,mp[15],zt[1<<12],L,dp[15][1<<12]; //mp 把地图反过来存 zt 存储所有状态 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x;
			cin>>x;
			mp[i]=(mp[i]<<1)+!x;//取反存储
		}
	}
	for(int i=0;i<(1<<m);i++){
		if(i&(i<<1)) continue;//相邻的有种草
		zt[++L]=i;//存储状态
	}
	dp[0][1]=1;//初始化
	for(int i=1;i<=n;i++){//枚举当前行
		for(int j=1;j<=L;j++){//枚举当前状态
			if(zt[j]&mp[i]) continue;//会与地图产生冲突则跳过
			for(int k=1;k<=L;k++){//枚举上行状态
				if(zt[j]&zt[k]||zt[k]&mp[i-1]) continue;//两行冲突或上行与上行地图会产生冲突则跳过
				dp[i][j]=(dp[i][j]+dp[i-1][k])%P;//状态转移
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=L;i++) ans=(ans+dp[n][i])%P;//求答案
	cout<<ans;
	return 0;
}

例题3：骨牌铺法/蒙德里安的梦想
和前面不同，我们考虑按列放置（即状态表示竖列）。
对于一个状态，我们把 $0$ 记为竖放， $1$ 记为横放；
那么，一个状态中若有连续的 $0$ 的个数为奇数，则不成立（因为 $0$ 为竖放，而竖放一块骨牌会占 $2$ 格，若连续 $0$ 的的数量为奇数，说明有半块骨牌），所以我们可以筛选所有合法的状态：

for(int i=0;i<(1<<n);i++){//枚举状态
    state[i]=1;//state标记状态i是否合法
    int cnt=0;//cnt统计连续0的数量
    for(int j=0;j<n;j++){//枚举所有骨牌
        if(i>>j&1){//如果是1
            if(cnt&1){//如果连续0的个数是奇数个
               state[i]=0; //状态不成立
            }
            cnt=0;//否则清0继续统计
        }else{//是0
            ++cnt;//统计连续0的个数
        }
    }
    if(cnt&1) state[i]=0;//特判最后一段
}

那么我们接下来考虑DP：

状态： $dp[i][j]$ 表示第 $i$ 列状态为 $j$ 的方案数；
转移方程：由于当前状态可以由上一列所有不会产生冲突的状态转移而来，
那怎么判断合法呢？首先，把两列合并，上列横放（ $1$ ），当前列必为空（ $0$ ）；上列竖放，这列为竖放或横放（ $1$ 或 $0$ ），所以，两行合并合法，则(j&k)==0；其次，如上述，j|k为 $1$ 必定是两列有一个横放，为 $0$ 则必定是两列都竖放，我们上面预处理过，连续的 $0$ 的个数不为奇数则成立，即state[j|k]。
所以状态转移方程为

$dp[i][j]=\sum_{i=0}^{L} dp[i-1][k]$

其中， $i$ 表示当前第 $i$ 列， $j$ 表示当前状态， $k$ 表示上一列状态；
3. 初始条件：我们可以初始化第0列一个也不放的情况：dp[0][0]=1;；
4. 循环顺序：我们第一层循环 $i$ ，表示第 $i$ 列，第二层循环 $j$ ，枚举当前状态，第三层循环 $k$ ，枚举上一列状态即可；
5. 由于数组最后一列无法横放，所有答案是 $dp[m][0]$ 。
最后放一下代码：

#include<bits/stdc++.h>
using namespace std;
const int max_n=15,max_m=(1<<15)+5;
int n,m,state[max_m];
long long dp[max_n][max_m];//dp开long long
int main(){
    cin>>n>>m;
    for(int i=0;i<(1<<n);i++){//预处理
        state[i]=1;
        int cnt=0;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                if(cnt&1){
                   state[i]=0; 
                }
                cnt=0;
            }else{
                ++cnt;
            }
        }
        if(cnt&1) state[i]=0;
    }
    dp[0][0]=1;//初始化
    for(int i=1;i<=m;i++){//枚举列
        for(int j=0;j<(1<<n);j++){//枚举当前列状态
            for(int k=0;k<(1<<n);k++){//枚举上列状态
                if((j&k)==0&&state[j|k]){//合法
                    dp[i][j]=dp[i][j]+dp[i-1][k];//转移
                }
            }
        }
    }
    cout<<dp[m][0];//输出
    return 0;
}

补充题：
[NOI2001] 炮兵阵地
 剑之试炼

4.2 集合式：

例题1：吃糖

对于每一包糖，我们可以用a[i]|=(1<<(w-1))把第 $i$ 包糖压缩为一个状态，便于我们完成“吃糖”的操作，所以：

cin>>n>>m>>k;
for(int i=1;i<=n;i++){
   for(int j=1;j<=k;j++){
       int w;
       cin>>w;
       a[i]|=(1<<(w-1));//把每包糖压缩为一个状态（把a[i]的第(w-1)位记为1）
   }
   dp[a[i]]=1;//初始化（见下文）
}

接下来考虑DP:

状态：我们用 $dp[i]$ 表示 $i$ 状态下选的最少的糖包数；
转移方程： $i$ 状态下选择第 $j$ 包糖的方案可以由当前状态转移，即：

$dp[i|a[j]]=min(dp[i|a[j]],dp[i]+1);$

其中i|a[j]表示 $i$ 状态下选择第 $j$ 包糖后的状态， $dp[i]+1$ 表示当前又选了一包糖；

初始条件：初始化每一包糖：dp[a[i]]=1;，什么也不放：dp[0]=1；
循环顺序：我们第一层循环 $i$ ，枚举状态，第二层循环 $j$ ，枚举当前糖果即可；
如果 $dp[1<<m-1]$ 没有更改，则说明无法凑齐 $m$ 包糖，输出 $-1$ ；否则输出 $dp[1<<m-1]$ 。

最后放个代码：

#include<bits/stdc++.h>
using namespace std;
const int maxx=1<<20;
int n,m,k,ans=1e9;
int a[105],dp[maxx];

int main(){
    memset(dp,0x3f,sizeof(dp));//赋为较大值
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            int w;
            cin>>w;
            a[i]|=(1<<(w-1));//存储糖果
        }
        dp[a[i]]=1;//初始化
    }
    dp[0]=0;//初始化
    for(int i=1;i<(1<<m);i++){//枚举m颗糖果的状态
        for(int j=1;j<=n;j++){//枚举糖果
            dp[i|a[j]]=min(dp[i|a[j]],dp[i]+1);//转移
        }
    }
    cout<<(dp[(1<<m)-1]==0x3f3f3f3f? -1: dp[(1<<m)-1]);//输出
    return 0;
}

例题2：小猫爬山
 [USACO12MAR]Cows in a Skyscraper G
两题一样（~~都也可以用记搜做~~），这里讲小猫爬山。
此题有两个因素：当前缆车剩余承重与缆车数，所有我们分别用两个数组记录；
接着考虑装态：状态 $i$ ， $1$ 表示猫已上缆车， $0$ 表示未上缆车；
最后考虑DP：‘

状态：我们用 $dp[i]$ 表示 $i$ 状态下使用的最少的缆车数，用 $c[i]$ 表示 $i$ 状态下所有的缆车中最大的剩余承重（贪心）；
转移方程：i|[a[j]表示该猫上缆车后的状态，然后 $dp$ 由当前状态转移最小值（更小的缆车数量）， $c$ 由当前转移最大值（更大的剩余承重）分两种情况：
一、能放：

$dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i])$

$c[i|(1<<(j-1))]=max(c[i]-a[j],c[i|(1<<(j-1))])$

二、不能放（再开辟一个缆车，所以 $dp$ 转移时 $dp[i]$ 要加 $1$ ）:

$dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);$

$c[i|(1<<(j-1))]=max(w-a[j],c[i|(1<<(j-1))]);$

初始条件：初始化缆车数：dp[0]=1，初始化缆车承重：c[0]=w；
循环顺序：我们第一层循环 $i$ ，枚举状态，第二层循环 $j$ ，枚举当前状态下未上车的猫即可；
输出 $dp[1<<n-1]$ 。

这样代码就有了：

#include<bits/stdc++.h>
using namespace std;
int n,w,a[20],dp[1<<18],c[1<<18];
int main(){
	cin>>n>>w;
    memset(dp,0x3f,sizeof(dp));//赋为较大值
	for(int i=1;i<=n;i++){
        cin>>a[i];
    }
	dp[0]=1,c[0]=w;	//初始化
	for(int i=0;i<(1<<n);i++){//枚举状态
		for(int j=1;j<=n;j++){//枚举猫
			if(i&(1<<(j-1))) continue;//上车了跳过
			if(c[i]>=a[j]){//能装下
				dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]);//转移
				c[i|(1<<(j-1))]=max(c[i]-a[j],c[i|(1<<(j-1))]);//转移
			}else{//装不下，再开一个缆车
				dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);//转移 +1再开一个缆车
				c[i|(1<<(j-1))]=max(w-a[j],c[i|(1<<(j-1))]);//状压 w-a[j]新开的缆车承重为w
			}
		}
	}
	cout<<dp[(1<<n)-1];//输出
	return 0;
}

例题3: 最短哈密顿路径
这题是个经典的状压DP题（当然也较难）
这一题不同于我们上面的状压DP，并没有上面几题的限制条件，同时状态定义也不好想。我们先考虑状态定义：

状态 $i$ 用 $1$ 表示该点走过，用 $0$ 表示该点走过没走过。

那我们现在来考虑DP：

状态：此处状态比较不好想，我们用 $dp[i][j]$ 表示 $i$ 状态下走过的点中终点为 $j$ 的最小距离；
转移方程：利用 $Floyd$ 的思想，当前点可以由上一个点过来，即：

$dp[i][j]=dp[x][k]_{min}$

其中 $i$ 表示当前状态， $j$ 表示当前终点， $x$ $=$ i&(~(1<<(j-1)))（把第 $j$ 位的标记改为没走过），表示上一个状态， $k$ 表示上一个点；

初始条件：标记起点：dp[1][0]=0;；
循环顺序：我们第一层循环 $i$ ，枚举状态，第二层循环 $j$ ，枚举当前终点，第三层循环 $k$ ，枚举上一个点即可；
显而易见，答案是 $dp[1<<n-1][n]$ ；
最后放一下代码：

#include<bits/stdc++.h>
using namespace std;
const int maxx=(1<<20)+5;
int n;
int mp[25][25],dp[maxx][25];
int main(){
    cin>>n;
    memset(dp,0x3f,sizeof(dp));//初始化为较大值
    for(int i=0;i<n;i++){//下标从0开始，方便左移
        for(int j=0;j<n;j++){
            cin>>mp[i][j];
        }
    }
    dp[1][0]=0;//初始化
    for(int i=1;i<(1<<n);i++){//枚举状态
        for(int j=0;j<n;j++){//枚举终点
            if(i>>j&1){//可以作为终点
                for(int k=0;k<n;k++){//就枚举上一点
                    if(j==k) continue;//重复跳过
                    if(i>>k&1){//上一点成立
                        dp[i][j]=min(dp[i][j],dp[i&(~(1<<j))][k]+mp[k][j]);//走过来
                    }
                }
            }
        }
    }
    cout<<dp[(1<<n)-1][n-1];//答案
    return 0;
}

补充题：
毕业旅行问题
 [NOIP2016 提高组] 愤怒的小鸟

No.5 后记

大家看完后，你学废了吗？
请大佬们奉上一个赞吧！
最后，祝大家2024CSP复赛rp++！ ACGO_顶呱呱

int f(){ rp--; return f()}

有帮助，赞一个

去预览

0/2000

全部评论 13

Macw07
顶

2024-10-21 来自美国
3
‮队团加不）ด้้童帅_者仇复
拼接质数都有了，为什么没有01背包（

2024-10-23 来自广东
1
- key0213
  回复‮队团加不）ด้้童帅_者仇复
  额，没想到，有空写写看
  
  2024-10-24 来自福建
  0
key0213
顶！

2024-10-22 来自福建
1
‮队团加不）ด้้童帅_者仇复
顶

2024-10-21 来自广东
1
小ZUZU_童瑞琪专属奴隶
666

2024-10-23 来自广东
0
key0213
顶！

2024-10-23 来自福建
0
key0213
顶！

2024-10-22 来自福建
0
天之神-复仇者_郑文越
顶

2024-10-22 来自浙江
0
李总
顶

2024-10-22 来自四川
0
Starsfocxy
顶

2024-10-22 来自江苏
0
key0213
顶！

2024-10-22 来自福建
0
key0213
顶！

2024-10-21 来自福建
0
key0213
顶！

2024-10-21 来自福建
0