狀壓講解部分參考博客狀壓 DP 詳解（位運算）
一、什麼是狀壓 dp？#
這裡是引用
狀壓 dp，即將狀態壓縮成 2 進制來保存，如矩陣中將一行的狀態壓縮成一個二進制串，如 dp [S][v] 中，S 可以代表已經訪問過的頂點的集合，v 可以代表當前所在的頂點為 v。S 代表的就是一種狀態（二進制表示）， (11001)~2~ 代表在二進制中 {0，3，4} 三個頂點已經訪問過了，(11001)~2~ 代表的十進制數就是 25 ，所以當 S 為 25 的時候其實就是代表已經訪問過了 {0，3，4} 三個頂點，那假如一共有 5 個頂點（標號為 01234）話，所有的頂點都訪問完畢，Sj 就是 (11111)~2~。
二、常用位運算#
對於上面的一些操作舉例一些
就如之上的 (11001)~2~ 來說是已經訪問了 0，3，4 三個頂點，當我接下去要訪問頂點 2 的話可以有以下操作：1. 看看第 3 位是什麼？那麼選擇取出二進制數 x 的第 k 位，y = x >>(k-1) & 1，y = (110)~2~ & 1 = 0，2. 把第 3 位變為 1，y = x | (1<<(k-1))，y = (11001)~2~ | (100)~2~ = (11101)~2~，所以頂點 2 訪問完畢，加入到集合 S 中也結束了，此時 S 為 (11101) 2 = 29。
三、例題#
A-Hie with the Pie#
題意#
給出所有地點之間來往的所需時間（來往時間可能不同），如何用最短時間送完所有地點的訂單並返回披薩店（編號 0）
思路#
先用 Floyd 算法得出最短路矩陣，用 S 表示狀態，dp [S][i] 表示送達第 i 個地點所需的最短時間，由 S 可知當前已送達哪些城市，S = 1<<N-1 即為全部送達的狀態（N 位全為 1）
代碼#
// A-Hie with the Pie
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 12;
const int inf = 0x3f3f3f;
int N,S,ans;
int dis[maxn][maxn];
int dp[1<<maxn][maxn];
void Floyd() {
for(int k = 0; k <= N; ++k) {
for(int i = 0; i <= N; ++i) {
for(int j = 0; j <= N; ++j) {
if(dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
}
int main(){
while(scanf("%d", &N) && N) {
for(int i = 0; i <= N; ++i) {
for(int j = 0; j <= N; ++j) {
scanf("%d", &dis[i][j]);
}
}
Floyd();
for(int S = 0; S < (1<<N); ++S) {//S的所有狀態
for(int i = 1; i <= N; ++i) {//所有要送的地點
if(S & ( 1<<(i-1) )) { //要送往地點i
if(S == ( 1<<(i-1) )) {//若S還沒有送往任何一個地點
dp[S][i] = dis[0][i];
break;
} else {
dp[S][i] = inf;
for(int j = 1; j <= N; ++j) {
if(j == i) continue;
//枚舉除當前要送往地點之外已送達地點，看時間是否更短
if(S&( 1<<(j-1) )) {
dp[S][i] = min(dp[S][i],dp[S^(1<<(i-1))][j] + dis[j][i]);
}
}
}
}
}
}
ans = inf;
for(int i = 1; i <= N; ++i) {
ans = min(ans, dp[(1<<N)-1][i] + dis[i][0]);
}
printf("%d\n",ans);
}
return 0;
}
B - Travelling#
題意#
給出 N 個城市、M 條道路成本，Acmer 先生想前往所有城市並且每個城市最多去兩次，求最低所需費用，若找不到這樣的路線則輸出 - 1
思路#
三進制狀壓 dp，每位上 0 表示沒去過，1 表示去過 1 次，2 表示去過 2 次，這裡用 cnt [i][j] 來表示 i 在 3 進制下從右往左第 j 位，用 three [i] 為三進制的第 i 位位權 即 three [i] 類似於二進制中 1<<i，最後若是全部訪問過且每個不超過 2 次則跟 ans 比較
代碼#
// B - Travelling
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 12;
const int maxt = 59049;
const int inf = 0x3f3f3f;
int N,M,S,ans;
int three[maxn];//three[i]為三進制的第i位最大值 類似於二進制中1<<i
int map[maxn][maxn];
int cnt[maxt][maxn];//cnt[i][j]表示i在3進制下從右往左第j位
int dp[maxt][maxn];//dp[i][j]表示i狀態下前往j城市後總費用
void init() {
memset(dp, -1, sizeof(dp));
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= N; ++j) {
map[i][j] = inf;
}
map[i][i] = 0;
}
}
int main(){
int x = 3;
three[0] = 0;
three[1] = 1;
for(int i = 2; i < maxn; ++i) {
three[i] = x;
x *= 3;
}
for(int i = 0; i < three[maxn-1]; ++i) {
int now = i;
for(int j = 1; j <= 10 && now; ++j) {
cnt[i][j] = now % 3;
now /= 3;
}
}
while(~scanf("%d %d", &N, &M)) {
init();
for(int i = 1; i <= M; ++i) {
int u,v,w;
scanf("%d %d %d", &u, &v, &w);
if(w < map[u][v]) {
map[u][v] = map[v][u] = w;
}
}
for(int i = 1; i <= N; ++i) {
dp[three[i]][i] = 0;
}
int ans = inf;
for(int S = 0; S < three[maxn-1]; ++S) {//S的所有狀態
bool allvis = true;
for(int i = 1; i <= N; ++i) {//枚舉每個城市
if(cnt[S][i] == 0) //該狀態下有城市還沒有被訪問過
allvis = false;
if(dp[S][i] == -1) continue;
for(int j = 1; j <= N; ++j) { //枚舉下個能訪問的城市
if(i == j || map[i][j] == inf || cnt[S][j] >= 2)
continue;
int nS = S+three[j];//下個狀態
if(dp[nS][j] == -1 || dp[S][i] + map[i][j] < dp[nS][j]) { //下個城市的總費用小
dp[nS][j] = dp[S][i] + map[i][j];
}
}
}
if(allvis) {
for(int i = 1; i <= N; ++i) {
if(dp[S][i] != -1) {
ans = min(ans, dp[S][i]);
}
}
}
}
if(ans == inf) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}