虐狗寶典學習筆記：

取出整數\(n\)在二進制表示下的第\(k\)位? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \((n >> k) & 1)\)

取出整數\(n\)在二進制表示下的第\(0 ~ k - 1\)位（后\(k\)位）? ? ? ? ? ? ? ? ? ? \(n & ((1 << k) - 1)\)

把整數\(n\)在二進制表示下的第\(k\)位取反? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \(n xor (1 << k)\)

對整數\(n\)在二進制表示下的第\(k\)為賦值\(1\)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \(n | (1 << k)\)

對整數\(n\)在二進制表示下的第\(k\)位賦值\(0\)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \(n & (~(1 << k))\)

?

CH0103---最短Hamilton路徑

http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0103%20%E6%9C%80%E7%9F%ADHamilton%E8%B7%AF%E5%BE%84

題意：

hamilton指的是每個節點經過一次且僅經過一次的路徑。現在路徑上有權值，問最短的路徑長度。

思路：

狀壓dp。\(dp[i][j]\)表示在狀態是\(i\)且最后一個經過的點時\(j\)時的最短路徑長度。

\(dp[i][j] = min{dp[i xor (i << j)][k] + weight(k, j)}\)

1 #include <bits/stdc++.h> 2 #define inf 0x3f3f3f3f 3 using namespace std; 4 typedef long long LL; 5 6 int n; 7 int g[25][25]; 8 int dp[1 << 20][25]; 9 10 int main() 11 { 12 scanf("%d", &n); 13 memset(dp, 0x3f, sizeof(dp)); 14 for(int i = 0; i < n; i++){ 15 for(int j = 0; j < n; j++){ 16 scanf("%d", &g[i][j]); 17 } 18 } 19 dp[1][0] = 0; 20 for(int i = 1; i < 1 << n; i++){ 21 for(int j = 0; j < n; j++){ 22 if(i >> j & 1){ 23 for(int k = 0; k < n; k++){ 24 if((i ^ 1 << j) >> k & 1){ 25 dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + g[k][j]); 26 } 27 } 28 } 29 } 30 } 31 32 printf("%d\n", dp[(1 << n) - 1][n - 1]); 33 return 0; 34 }

?

?

poj2288---Islands and Bridges

http://poj.org/problem?id=2288

題意：

有n個島，m座橋。每座島有一個val，一條漢密爾頓路徑的值是路徑中所有點的val之和，加上所有路徑上相鄰的兩個島的val乘積之和，加上路徑上相鄰的三個島的val乘積之和。求最大的值以及方案數。

思路：

和CH0103很相近，不同的是這道題要多存一個島。\(dp[stat][i][j]\)表示當前狀態是\(stat\)，最后一個走的島是\(j\),倒數第二個走的島是\(i\), \(num\)數組表示對應的方案數。

當\( (stat, i, j) \)可達時，我們檢查下一個要走的島\(k\)，如果此時\( (stat >> k) & 1 == 0 \) 且 \( g[j][k] == 1 \)說明\(k\)是滿足條件的

設\(tmp\)是下一個走\(k\)時的總價值。那么，\(dp[stat | (1 << k)][j][k] = max(dp[stat | (1 << k)][j][k], tmp)\)

如果\(tmp == dp[stat | (1 << k)][j][k]\),那么，\(num[stat | (1 << k)][j][k] += num[stat][i][j]\)。否則\(num[stat | (1 << k)][j][k] = num[stat][i][j] \)

那么要如何求\(tmp\) 呢。

首先當\(j\)可以走到\(k\)時，肯定有 \(tmp = dp[stat][i][j] + val[k] + val[j] * val[k] \)

如果此時還有\(g[i][k] == 1\) 那么\(tmp += val[i] * val[j] * val[k]\)

最后我們對于\(stat = (1 << n) - 1\)枚舉\(i\)和\(j\)，找到最大的結果。

注意方案數會超出int。還需要注意\(n = 1\)時的特殊情況。

注意內存省著點，會MLE

1 //#include <bits/stdc++.h> 2 #include <iostream> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <stdio.h> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #define inf 0x3f3f3f3f 11 using namespace std; 12 typedef long long LL; 13 14 int n, m, q; 15 bool g[13][13]; 16 int dp[1 << 13][13][13]; 17 LL num[1 << 13][13][13]; 18 int val[13]; 19 int cnt; 20 21 void hamilton() 22 { 23 memset(dp, -1, sizeof(dp)); 24 memset(num, 0, sizeof(num)); 25 for(int i = 0; i < n; i++){ 26 for(int j = 0; j < n; j++){ 27 if(g[i][j]){ 28 dp[1 << i | 1 << j][i][j] = val[i] + val[j] + val[i] * val[j]; 29 num[1 << i | 1 << j][i][j] = 1; 30 } 31 } 32 } 33 34 for(int stat = 1; stat < 1 << n; stat++){ 35 for(int i = 0; i < n; i++){ 36 if((stat >> i) & 1){ 37 for(int j = 0; j < n; j++){ 38 if((stat >> j) & 1){ 39 if(g[i][j] && dp[stat][i][j] != -1){ 40 for(int k = 0; k < n; k++){ 41 if(g[j][k] && k != i && ((stat >> k) & 1) == 0){ 42 int tmp = dp[stat][i][j] + val[k] + val[k] * val[j]; 43 if(g[i][k]){ 44 tmp += val[i] * val[j] * val[k]; 45 } 46 if(tmp > dp[stat | (1 << k)][j][k]){ 47 dp[stat | (1 << k)][j][k] = tmp; 48 num[stat | (1 << k)][j][k] = num[stat][i][j]; 49 } 50 else if(tmp == dp[stat | (1 << k)][j][k]){ 51 num[stat | (1 << k)][j][k] += num[stat][i][j]; 52 } 53 } 54 } 55 } 56 } 57 } 58 } 59 } 60 } 61 //return dp[(1 << n) - 1][n - 1]; 62 } 63 64 int main() 65 { 66 scanf("%d", &q); 67 while(q--){ 68 memset(g, 0, sizeof(g)); 69 scanf("%d%d", &n, &m); 70 for(int i = 0; i < n; i++){ 71 scanf("%d", &val[i]); 72 } 73 for(int i = 0; i < m; i++){ 74 int u, v; 75 scanf("%d%d", &u, &v); 76 g[u - 1][v - 1] = 1; 77 g[v - 1][u - 1] = 1; 78 } 79 if(n == 1){ 80 printf("%d 1\n", val[0]); 81 continue; 82 } 83 84 hamilton(); 85 int maxi = 0; 86 LL ans = 0; 87 for(int i = 0; i < n; i++){ 88 for(int j = 0; j < n; j++){ 89 if(g[i][j]){ 90 if(maxi < dp[(1 << n) - 1][i][j]){ 91 maxi = dp[(1 << n) - 1][i][j]; 92 ans = num[(1 << n) - 1][i][j]; 93 } 94 else if(maxi == dp[(1 << n) - 1][i][j]){ 95 ans += num[(1 << n) - 1][i][j]; 96 } 97 } 98 } 99 } 100 101 printf("%d %lld\n", maxi, ans / 2); 102 } 103 return 0; 104 }

?

轉載于:https://www.cnblogs.com/wyboooo/p/9932142.html

總結

以上是生活随笔為你收集整理的CH0103最短Hamilton路径 poj2288 Islands and Brigdes【状压DP】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。