前几天刚写了一道状压DP入门题，结果这次就遇到了，在比赛最后一点时间一眼看破，无奈只有想法，写不来……
不过赛后尝试写的时候遇到了一个自己不会的问题，也就是说假如比赛的时候开了这道题，我也会一直卡着。
题意：
给你很多个行李的位置和起点的位置，要你把所有行李搬运到起点，一次只能搬一个或者两个，花费是距离，求最小花费。行李最多24个。
思路
状压dp，对于每一个状态，我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的，那么，我通过从小到大枚举状态，在保证我当前状态最优的前提下，由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举，找到第一个它能够搬运的行李，每次都拓展这个状态即可。
AC Code
#include <bits/stdc++.h>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))
using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int max_n = 30;
const int max_m = 1 << 24;
int n, tmp;
int dp[max_m], pre[max_m];
pii nodes[max_n];
int dis[max_n][max_n];
inline int calcul(int a, int b)
{
return (nodes[a].first - nodes[b].first) * (nodes[a].first - nodes[b].first) + (nodes[a].second - nodes[b].second) * (nodes[a].second - nodes[b].second);
}
int main()
{
scanf("%d %d %d", &nodes[29].first, &nodes[29].second, &n);
nodes[n] = nodes[29];
each(i, n) scanf("%d %d", &nodes[i].first, &nodes[i].second);
each(i, n + 1) range(j, i + 1, n) dis[i][j] = dis[j][i] = calcul(i, j);
fill(dp, 0x3f), dp[0] = 0;
each(i, (1 << n)) if (dp[i] != inf) each(j, n) if (!(i & (1 << j)))
{
int t = (i | (1 << j));
if (dp[t] > (tmp = dp[i] + 2 * dis[j][n])) {
dp[t] = tmp;
pre[t] = i;
}
each(k, n) if (!(t & (1 << k)))
{
int p = (t | (1 << k));
if (dp[p] > (tmp = dp[i] + dis[k][n] + dis[j][n] + dis[k][j])) {
dp[p] = tmp;
pre[p] = i;
}
}
break ;
}
int cur = (1 << n) - 1, ps, det;
printf("%d\n0 ", dp[cur]);
while (cur != 0) {
ps = pre[cur];
det = cur - ps;
each(i, n) if (det & (1 << i)) printf("%d ", i + 1);
printf("0 ");
cur = ps;
}
return 0;
}