「AT1728」「CODE FESTIVAL 2015 OKINAWA OPEN」Falconry
题目传送门
题意
给定平面上 \(n\) 个点 \((x_i,y_i)\)，以及三只鸟的初始坐标 \((x_a,y_a),(x_b,y_b),(x_c,y_c)\)。现在三只鸟要从初始点开始，依次飞到一些点（不需要回到起点），要求每个点至少被一只鸟飞到。求三只鸟总飞行距离之和的最小值。
从一个点 \((x_s,y_s)\) 飞到另一个点 \((x_t,y_t)\) 的飞行距离为这两个点的欧几里得距离，即 \[\sqrt{(x_s - x_t)^2 + (y_s - y_t)^2}\]
\(n\le 18\)，所有横纵坐标的绝对值 \(\le 10^4\)，时限 \(8s\)。
方法一
三只鸟很难考虑，考虑一只鸟飞遍某个点集所需的最少时间。
记 \(dp_{t,i,j}\) 表示第 \(t\) 只鸟，飞遍点集 \(i\)，最后停留在点 \(j\) 的最小距离和。
转移很显然，只要在点集 \(i\) 中枚举上一个点 \(k\)，然后直接转移即可。
最后枚举每只鸟飞到的点集即可，因为两只鸟飞到的点集不会有交，所以复杂度为 \(O(3^n)\)。具体实现时，可以枚举一个集合 \(A\)，再枚举这个集合的子集 \(B\)，假设全集为 \(C\)，则三个集合分别为 \(B,A-B,C-A\)。
时间复杂度 \(O(3n^22^n+3^n)\)，常数不大，最大点 \(2898ms\)（评测记录）。
方法二
发现上面的方法比较慢，且主要在于 \(3^n\) 的统计答案。考虑直接在第二只鸟、第三只鸟 DP 时，直接合并答案。
记 \(dp_{t,i,j}\) 表示前 \(i\) 只鸟，飞遍点集 \(i\)，第 \(i\) 只鸟停留在点 \(j\) 时的最小距离和。
主要转移方程与方法一差不多，但是有一些细节需要注意，例如飞到第一个点时需要特殊转移，具体参见代码。也许有更好的、细节更少的写法，欢迎分享。
时间复杂度 \(O(3n^22^n)\)，最大点 \(535ms\)（评测记录）。
代码
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
int n;
struct point{
int x, y;
}a[20], b[3];
double Dp[3][300000][20];
double dis(point a, point b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main(){
scanf("%d", &n);
for (register int i = 0; i < n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
for (register int i = 0; i < 3; ++i) scanf("%d%d", &b[i].x, &b[i].y);
for (register int t = 0; t < 3; ++t){
double (*dp)[20] = Dp[t];
for (register int i = 0; i < (1 << n); ++i)
for (register int j = 0; j <= n; ++j)
dp[i][j] = 1e100;
dp[0][n] = 0;
for (register int i = 0; i < n; ++i) dp[1 << i][i] = dis(b[t], a[i]);
for (register int i = 0; i < (1 << n); ++i)
for (register int j = 0; j < n; ++j)
if (i >> j & 1){
for (register int k = 0; k < n; ++k)
if (i >> k & 1 && k != j)
dp[i][j] = std :: min(dp[i][j], dp[1 << j ^ i][k] + dis(a[k], a[j]));
dp[i][n] = std :: min(dp[i][n], dp[i][j]);
}
}
double ans = 1e100;
for (register int i = 0; i < (1 << n); ++i)
for (register int j = i; j >= 0; j = (j - 1) & i){
int A = j, B = i ^ j, C = ((1 << n) - 1) ^ i;
ans = std :: min(ans, Dp[0][A][n] + Dp[1][B][n] + Dp[2][C][n]);
if (!j) break;
}
printf("%.12lf\n", ans);
}
|
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
int n;
struct point{
int x, y;
}a[20], b;
double dp[3][300000][20], d[20][20];
double dis(point a, point b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main(){
scanf("%d", &n);
for (register int i = 0; i < n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
for (register int t = 0; t < 3; ++t){
scanf("%d%d", &b.x, &b.y);
for (register int i = 0; i < (1 << n); ++i)
for (register int j = 0; j <= n; ++j)
dp[t][i][j] = 1e100;
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < n; ++j)
d[i][j] = dis(a[i], a[j]);
dp[t][0][n] = 0;
for (register int i = 0; i < n; ++i) dp[t][1 << i][i] = dis(b, a[i]);
for (register int i = 0; i < (1 << n); ++i)
for (register int j = 0; j < n; ++j)
if (i >> j & 1){
dp[t][i][n] = std :: min(t ? dp[t - 1][i][n] : 1e100, dp[t][i][n]);
for (register int k = 0; k < n; ++k)
if (i >> k & 1 && k != j)
dp[t][i][j] = std :: min(dp[t][i][j], dp[t][1 << j ^ i][k] + d[k][j]);
dp[t][i][j] = std :: min(dp[t][i][j], t ? dp[t - 1][1 << j ^ i][n] + dis(b, a[j]) : 1e100);
dp[t][i][n] = std :: min(dp[t][i][n], dp[t][i][j]);
}
}
printf("%.12lf\n", dp[2][(1 << n) - 1][n]);
}
|
有更好的写法或复杂度更优的做法请在评论中分享！
