题目地址：Codeforces：Problem – 8C – Codeforces、洛谷：CF8C Looking for Order – 洛谷 | 计算机科学教育新生态

题目描述

Girl Lena likes it when everything is in order, and looks for order everywhere. Once she was getting ready for the University and noticed that the room was in a mess — all the objects from her handbag were thrown about the room. Of course, she wanted to put them back into her handbag. The problem is that the girl cannot carry more than two objects at a time, and cannot move the handbag. Also, if he has taken an object, she cannot put it anywhere except her handbag — her inherent sense of order does not let her do so.

You are given the coordinates of the handbag and the coordinates of the objects in some Сartesian coordinate system. It is known that the girl covers the distance between any two objects in the time equal to the squared length of the segment between the points of the objects. It is also known that initially the coordinates of the girl and the handbag are the same. You are asked to find such an order of actions, that the girl can put all the objects back into her handbag in a minimum time period.

题意简述

在二维平面上散落着许多物品，你需要把这些物品捡起并放回指定位置的包里，初始时你在包的位置上，你可以移动到任意点，移动的时间为两点间距离的平方，且在任何时候，你的手里最多只能拿不超过2个物品。求把所有物品放回包里的最短时间。

输入输出格式

输入格式：

The first line of the input file contains the handbag’s coordinates x_s, y_s. The second line contains number n (1 ≤ n ≤ 24) — the amount of objects the girl has. The following n lines contain the objects’ coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.

输出格式：

In the first line output the only number — the minimum time the girl needs to put the objects into her handbag.

In the second line output the possible optimum way for Lena. Each object in the input is described by its index number (from 1 to n), the handbag’s point is described by number 0. The path should start and end in the handbag’s point. If there are several optimal paths, print any of them.

输入输出样例

输入样例#1：

0 0
2
1 1
-1 1

输出样例#1：

8
0 1 2 0 

输入样例#2：

1 1
3
4 3
3 4
0 0

输出样例#2：

32
0 1 2 0 3 0 

题解

数据范围+直觉判断首先得是个状压。

首先从包位置出发，每次选择两个物品，两个物品的先后次序不会影响答案，且不同的两个物品的组合的先后次序也不会影响答案，这条性质会用在之后的一个优化中，现在暂且放在这里。

考虑状压DP，$f(S)$表示已经放进包里的物品的状态为$S$，枚举两个（可以相同，用来表示只拿取了一个物品的情况）不在状态$S$中的物品$i, j$，令包的位置为第0个物品所在位置，$\operatorname{dist}(i, j)$表示从$i$物品到$j$物品所在位置的移动需要的时间，有以下转移

$$ f(S \operatorname{or} 2^{i-1} \operatorname{or} 2^{j-1}) = \min \{ f(S \operatorname{or} 2^{i-1} \operatorname{or} 2^{j-1}), f(S) + \operatorname{dist}(0, i) + \operatorname{dist}(i, j) + \operatorname{dist}(j, 0) \} $$

初始时令所有DP值为极大值，且$f(0)=0$即可。这种算法的复杂度是$O(2^n \cdot n^2)$的，并不能通过本题。

接下来考虑对原算法的优化，由于不同的两个物品的组合的先后次序也不会影响答案，每个物品都必须被拾起取回包中，实际上每次转移只需要找到一个不在$S$中的物品$i$，枚举每一个不在$S$中的物品$j$进行转移就可以了。如果按照以前的逻辑计算，则由于拾取物品$i$的先后次序会很多，答案相同而次序不同的方案会被计算多次，这样优化后只会被计算一次，既保证了答案的正确性又优化了复杂度。

优化后的复杂度是$O(2^n \cdot n)$，由于本题时限设置为4s，还是能通过的。

代码

// Code by KSkun, 2019/8
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
	static char buf[100000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
		? EOF : *p1++;
}

inline LL readint() {
	LL res = 0, neg = 1; char c = fgc();
	for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
	for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
	return res * neg;
}

inline char readsingle() {
	char c;
	while(!isgraph(c = fgc())) {}
	return c;
}

const int MAXN = 25;
const int INF = 0x3f3f3f3f;

int n, dp[1 << MAXN], pre[1 << MAXN], x[MAXN], y[MAXN], dis[MAXN][MAXN];
std::vector<int> ans;

inline int distance(int a, int b) {
	return (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);
}

int main() {
	x[0] = readint(); y[0] = readint();
	n = readint();
	for(int i = 1; i <= n; i++) {
		x[i] = readint(); y[i] = readint();
	}
	for(int i = 0; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			dis[i][j] = dis[j][i] = distance(i, j);
		}
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for(int s = 0; s < (1 << n); s++) {
		if(dp[s] >= INF) continue;
		for(int i = 1; i <= n; i++) {
			if(s & 1 << i - 1) continue;
			for(int j = 1; j <= n; j++) {
				if(s & 1 << j - 1) continue;
				if(dp[s | 1 << i - 1 | 1 << j - 1] > dp[s] + dis[0][i] + dis[i][j] + dis[j][0]) {
					dp[s | 1 << i - 1 | 1 << j - 1] = dp[s] + dis[0][i] + dis[i][j] + dis[j][0];
					pre[s | 1 << i - 1 | 1 << j - 1] = s;
				}
			}
			break;
		}
	}
	printf("%d\n", dp[(1 << n) - 1]);
	int s = (1 << n) - 1;
	while(s) {
		int p = pre[s], t = s ^ p, cnt = 1, t1 = 0, t2 = 0;
		while(t) {
			if((t & 1) == 1) {
				if(t1) t2 = cnt;
				else t1 = cnt;
			}
			t >>= 1; cnt++;
		}
		ans.push_back(0);
		if(t1) ans.push_back(t1);
		if(t2) ans.push_back(t2);
		s = p; p = pre[s];
	}
	ans.push_back(0);
	std::reverse(ans.begin(), ans.end());
	for(auto i : ans) {
		printf("%d ", i);
	}
	return 0;
}