前置
此处仅为简写，详见OI Wiki
位运算
- 按位与 (&)：
1 & 1 = 1,1 & 0 = 0,0 & 0 = 0 - 按位或 (|)：
1 | 1 = 1,1 | 0 = 1,0 | 0 = 0 - 位取反 (~)：
~ 1 = 0，~ 0 = 1 - 按位异或 (^)：
1 ^ 1 = 0,0 ^ 0 = 0,1 ^ 0 = 1,0 ^ 1 = 1 - 左移 (<<)：
1<<1 = 10,1<<2 = 100 - 右移 (>>)：
100>>1 = 10,100>>2 = 1
特殊运算
给定一个十进制数 \(x\)：
-
判断 \(x\) 的第 \(i\) 位是否为 \(1\)：
x&(1<<i) -
将 \(x\) 的第 \(i\) 位改为 1：
x|(1<<i) -
将 \(x\) 的第 \(i\) 为改为 0：
x&(~(1<<i)) -
将 \(x\) 的第 \(i\) 为取反：
x^(1<<i)
状压DP-Hamilton通路问题
例题1
一眼看，可以发现暴力做法就是全排列问题，枚举一遍取最优解
但是16！(不是感叹号是阶乘) 的运算次数显然不够我们造，所以我们要考虑优化
我们可以发现，当我们到达一个点时，我们实际上并不关注前面经过了哪些点，只要知道最后一个点的位置增加距离即可
所以考虑DP
-
定义状态：定义\(dp_{status,i}\)表示在\(status\)(二进制)状态下，以\(i\)结尾的答案最小值(\(status\)用\(1\)表示已经走过，\(0\)表示没走过)，同时，因为有二进制，我们下标从0开始
-
确定答案：\(dp_{(1<<n)-1,n-1}\)，前一个表示了一个长度为\(n\)的全为\(1\)的二进制串,同时下标是\(0\)到\(n-1\)，所以结尾是\(n-1\)
-
确定状态转移方程：\(dp_{status,i}=\min(dp_{status,i},dp_{status^(1<<i),j} +dis_{j,i})\)（在代码中解释）
-
边界及初始值：\(dp_{i,j}=\inf\)，\(dp_{1,0}=0\)
代码（附解释）：
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e2+5,mod=1e9+7,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int dp[(1<<17)-1][20];
int n;
int val[maxn][maxn];
signed main(){cin>>n; for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>val[i][j];//输入距离}}memset(dp,0x3f3f3f3f,sizeof(dp));//边界dp[1][0]=0;//初始化for(int status=2;status<(1<<n);status++){//枚举所有状态for(int i=0;i<n;i++){//枚举状态中的每一位if((status>>i)&1){//判断i位是否为1for(int j=0;j<n;j++){//枚举其他位int tmp=status^(1<<i);//上一个状态if(i!=j&&(tmp>>j)&1){//判断上一个状态中j位是否为1dp[status][i]=min(dp[status][i],dp[tmp][j]+val[j][i]);//状态转移}}}}}cout<<dp[(1<<n)-1][n-1];//答案return 0;
}
习题1
与上一题类似，只是终点与起点一样，我们枚举起点外的所有点，选一个答案+回来路径最小的点，输出答案即可：
代码：
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e3+5,mod=1e9+7,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int dp[(1<<21)-1][25];
int n;
int val[maxn][maxn];
signed main(){cin>>n; for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>val[i][j];}}memset(dp,0x3f3f3f3f,sizeof(dp));dp[1][0]=0;for(int status=2;status<(1<<n);status++){for(int i=0;i<n;i++){if((status>>i)&1){for(int j=0;j<n;j++){int tmp=status^(1<<i);if(i!=j&&(tmp>>j)&1){dp[status][i]=min(dp[status][i],dp[tmp][j]+val[j][i]);}}}}}//DP过程int maxi=1e9;for(int i=1;i<n;i++){//枚举除起点外每个点if(dp[(1<<n)-1][i]+val[i][0]<maxi){//打擂台求最小值（这里变量写成最大值了）maxi=dp[(1<<n)-1][i]+val[i][0];}}cout<<maxi;return 0;
}