http://codeforces.com/contest/8/problem/C
题目大意：给你一个坐标系，给你一个人的目前的坐标（该坐标也是垃圾桶的坐标），再给你n个垃圾的坐标，这个人要捡完所有的垃圾，而且每次最多只能捡两个，然后把他扔到垃圾桶里面去。问这个人捡完所有垃圾所需要的最短的路程是多少？（路程=两个坐标之间连线距离的平方）
思路：貌似是简单的状压dp？
我们枚举一下1<<n就好了，然后每次都取最高位和其他的某一个进行匹配即可（而不用取其他位，因为其他位在之前就已经枚举过了）。
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = ;
int dp[ << maxn], par[ << maxn];
pair<int, int> girl, a[maxn + ];
int n; inline int get_high(int val){///1需要右移几位
int pos = ;
while (val){
val >>= ; pos++;
}
return pos - ;
} inline int dis(int x, int y){
if (x == -)
return (girl.fi - a[y].fi) * (girl.fi - a[y].fi) + (girl.se - a[y].se) * (girl.se - a[y].se);
return (a[x].fi - a[y].fi) * (a[x].fi - a[y].fi) + (a[x].se - a[y].se) * (a[x].se - a[y].se);
} int main(){
///int high = get_high(4); pos = 2 4 = 100
scanf("%d%d", &girl.fi, &girl.se);
cin >> n;
for (int i = ; i < n; i++){
int x, y; scanf("%d%d", &x, &y);
a[i] = mk(x, y);
}
memset(dp, 0x3f, sizeof(dp));
memset(par, -, sizeof(par));
dp[] = ;
for (int i = ; i < ( << n); i++){
int high = get_high(i);///最高位是第几位
dp[i] = min(dp[i], dp[i ^ ( << high)] + dis(-, high) * );
par[i] = i ^ ( << high);
for (int j = ; j < high; j++){
if (i & ( << j)) {
int tmp = dp[i ^ ( << j) ^ ( << high)] + dis(j, high) + dis(-, j) + dis(-, high);
if (dp[i] > tmp){
dp[i] = tmp; par[i] = i ^ ( << j) ^ ( << high);
}
}
}
}
printf("%d\n", dp[( << n) - ]);
int tmp = ( << n) - ;
printf("0 ");
for (int i = par[tmp]; i != -; i = par[i]){
int val = tmp ^ i;
int pos = ;
while (val){
if (val & ) printf("%d ", pos + );
val >>= ; pos++;
}
printf("0 ");
tmp = i;
}
cout << endl;
return ;
}