文章目錄

• • • 題目解答
    • 題目鏈接

題目解答

分析：

狀態(tài)壓縮dp是用二進(jìn)制數(shù)來(lái)表示狀態(tài)。
數(shù)據(jù)范圍n = 20， 那么狀態(tài)總量就是$2^{20}$個(gè)狀態(tài)。

可以按照以下思路去思考：

哪些點(diǎn)被用過(guò)

當(dāng)前停在哪個(gè)點(diǎn)上

狀態(tài)表示

$f[i][j]$表示狀態(tài)為i，且停在點(diǎn)j的最短Hamilton路徑的長(zhǎng)度。

狀態(tài)轉(zhuǎn)移：

state_k 是1個(gè)狀態(tài)的集合，其中不包括狀態(tài)j， f[state][j] = f[state_k][k] + weight[k][j]

補(bǔ)充一個(gè)常用的技巧：

i >> j & 1

這里的運(yùn)算優(yōu)先級(jí)需要知道： 右移運(yùn)算符(>>)的優(yōu)先級(jí)高于 位運(yùn)算，所以這里先計(jì)算(i >> j),含義是i的二進(jìn)制表示右移j位，也就是找到了i的第j位，然后與1(&1)，含義是判斷這一位是否為1.（當(dāng)然，這里的位，都是指二進(jìn)制下的某一位）。

綜上，i >> j & 1表示 i的二進(jìn)制表示中第j位是否為1.

同樣的道理，讀者可以分析一下下面這句代碼

i -(1 << j) >> k & 1

提示： 減法優(yōu)先級(jí) 高于 右移(>>),右移(>>)優(yōu)先級(jí)高于 位運(yùn)算與(&)，上面這句話等同于

(i - (1 << j)) >> k & 1

ac代碼

#include<bits/stdc++.h> using namespace std;const int N = 20, M = 1 << 20; // 狀態(tài) int n; // f[i][j] 表示狀態(tài)是i 的情況下，停在點(diǎn)j時(shí)的最短路徑是多少 int f[M][N], weight[N][N]; // 邊權(quán)int main(){cin >> n;for(int i = 0; i < n; i ++)for(int j = 0; j < n; j++)cin >> weight[i][j];memset(f, 0x3f, sizeof f);f[1][0] = 0; for(int i = 0; i< 1 << n; i ++){for(int j = 0; j < n; j ++){if( i >> j & 1) //判斷整數(shù)二進(jìn)制表示的第j位是否是1for(int k = 0; k < n; k ++){// 看一下state_k 這個(gè)狀態(tài)// 減法優(yōu)先級(jí) 高于 右移>>,右移優(yōu)先級(jí)高于 位運(yùn)算&if( i -(1 << j) >> k & 1)f[i][j] = min(f[i][j], f[i - (1<< j)][k] + weight[k][j]);}}}// 把所有點(diǎn)都遍歷過(guò)，并且停在了n-1這個(gè)點(diǎn)cout << f[(1 << n) -1][n -1] << endl; }

題目鏈接

https://www.acwing.com/problem/content/93/

總結(jié)

以上是生活随笔為你收集整理的《算法竞赛进阶指南》打卡-基本算法-AcWing 91. 最短Hamilton路径:位运算、状态压缩dp、dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。