虐狗宝典学习笔记：
取出整数\(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路径
题意：
hamilton指的是每个节点经过一次且仅经过一次的路径。现在路径上有权值，问最短的路径长度。
思路：
状压dp。\(dp[i][j]\)表示在状态是\(i\)且最后一个经过的点时\(j\)时的最短路径长度。
\(dp[i][j] = min{dp[i xor (i << j)][k] + weight(k, j)}\)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL; int n;
int g[][];
int dp[ << ][]; int main()
{
scanf("%d", &n);
memset(dp, 0x3f, sizeof(dp));
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
scanf("%d", &g[i][j]);
}
}
dp[][] = ;
for(int i = ; i < << n; i++){
for(int j = ; j < n; j++){
if(i >> j & ){
for(int k = ; k < n; k++){
if((i ^ << j) >> k & ){
dp[i][j] = min(dp[i][j], dp[i ^ << j][k] + g[k][j]);
}
}
}
}
} printf("%d\n", dp[( << n) - ][n - ]);
return ;
}
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
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL; int n, m, q;
bool g[][];
int dp[ << ][][];
LL num[ << ][][];
int val[];
int cnt; void hamilton()
{
memset(dp, -, sizeof(dp));
memset(num, , sizeof(num));
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(g[i][j]){
dp[ << i | << j][i][j] = val[i] + val[j] + val[i] * val[j];
num[ << i | << j][i][j] = ;
}
}
} for(int stat = ; stat < << n; stat++){
for(int i = ; i < n; i++){
if((stat >> i) & ){
for(int j = ; j < n; j++){
if((stat >> j) & ){
if(g[i][j] && dp[stat][i][j] != -){
for(int k = ; k < n; k++){
if(g[j][k] && k != i && ((stat >> k) & ) == ){
int tmp = dp[stat][i][j] + val[k] + val[k] * val[j];
if(g[i][k]){
tmp += val[i] * val[j] * val[k];
}
if(tmp > dp[stat | ( << k)][j][k]){
dp[stat | ( << k)][j][k] = tmp;
num[stat | ( << k)][j][k] = num[stat][i][j];
}
else if(tmp == dp[stat | ( << k)][j][k]){
num[stat | ( << k)][j][k] += num[stat][i][j];
}
}
}
}
}
}
}
}
}
//return dp[(1 << n) - 1][n - 1];
} int main()
{
scanf("%d", &q);
while(q--){
memset(g, , sizeof(g));
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++){
scanf("%d", &val[i]);
}
for(int i = ; i < m; i++){
int u, v;
scanf("%d%d", &u, &v);
g[u - ][v - ] = ;
g[v - ][u - ] = ;
}
if(n == ){
printf("%d 1\n", val[]);
continue;
} hamilton();
int maxi = ;
LL ans = ;
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(g[i][j]){
if(maxi < dp[( << n) - ][i][j]){
maxi = dp[( << n) - ][i][j];
ans = num[( << n) - ][i][j];
}
else if(maxi == dp[( << n) - ][i][j]){
ans += num[( << n) - ][i][j];
}
}
}
} printf("%d %lld\n", maxi, ans / );
}
return ;
}