LG-P9119 [春季测试 2023] 圣诞树 Solution

更好的阅读体验戳此进入

游记戳此进入

题面

给定平面内凸包，最小化从其最高点开始的任意哈密尔顿路径（认为任意两点之间均可到达）的欧几里得距离，输出最小化的方案。存在 SPJ。

Solution

首先对于 $n\le 18$$n \le 18$，不难发现其为经典的 TSP 问题，状压后简单转移一下即可。对于性质 B，顺序输出即可。对于性质 A，目前没想到什么正确的思路。

考虑正解，发现对于任意两条路径一定不相交，证明是显然的，考虑任意四个点：

显然由于三角形两边之和大于第三边，前者一定优于后者。

所以对于逆时针给定的若干个点，当处于 $i$$i$ 时，最优决策一定只能是下一步到 $i-1$$i - 1$ 或 $i+1$$i + 1$，否则将会存在一个点被隔离，导致最终去往该点时一定形成交叉路径。

于是此时问题显然地转化为了区间 DP，考虑将原序列倍长，设状态 $dp(l,r,0/1)$$dp(l, r, 0/1)$ 表示当前已经走过了 $[l,r]$$[l, r]$ 的点，且最后停在了 $l$$l$ 或 $r$$r$ 的最小的总距离，则显然对于起点 $s$$s$ 有 $dp(s,s,0)=0,dp(s,s,1)=0$$dp(s, s, 0) = 0, dp(s, s, 1) = 0$。

转移也十分显然，与 [ABC273F] Hammer 2 类似，即：

Code

xxxxxxxxxx
97
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N;
27
pair < ld, ld > pts[2100];
28
ld dis[2100][2100];
29
ld dp[2100][2100][2];
30
tuple < int, int, int > frm[2100][2100][2];
31
int top(-1); ld topy(-1e8);
32

33
int main(){
34
    auto CalDis = [](pair < ld, ld > a, pair < ld, ld > b)->ld{
35
        return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
36
    };
37
    auto Update = [](int l, int r, int k, int sl, int sr, int sk, int dl, int dr)->void{
38
        if(dp[sl][sr][sk] >= 1e12)return;
39
        if(dp[sl][sr][sk] + dis[dl][dr] < dp[l][r][k])
40
            dp[l][r][k] = dp[sl][sr][sk] + dis[dl][dr], frm[l][r][k] = {sl, sr, sk};
41
    };
42

43
    for(int i = 0; i <= 2010; ++i)for(int j = 0; j <= 2010; ++j)for(int k = 0; k <= 1; ++k)dp[i][j][k] = 1e12;
44
    N = read();
45
    for(int i = 1; i <= N; ++i){
46
        scanf("%Lf%Lf", &pts[i].first, &pts[i].second);
47
        pts[i + N] = pts[i];
48
        if(pts[i].second > topy)topy = pts[i].second, top = i;
49
    }
50
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)
51
        dis[i][j] = dis[i + N][j] = dis[i][j + N] = dis[i + N][j + N] = CalDis(pts[i], pts[j]);
52
    dp[top][top][0] = dp[top][top][1] = dp[top + N][top + N][0] = dp[top + N][top + N][1] = 0.0;
53
    for(int len = 2; len <= N; ++len)
54
        for(int l = 1; l <= (N << 1) - len + 1; ++l){
55
            int r = l + len - 1;
56
            Update(l, r, 0, l + 1, r, 0, l + 1, l);
57
            Update(l, r, 0, l + 1, r, 1, r, l);
58
            Update(l, r, 1, l, r - 1, 0, l, r);
59
            Update(l, r, 1, l, r - 1, 1, r - 1, r);
60
        }
61
    ld ansv(1e12); tuple < int, int, int > curp(0, 0, 0);
62
    for(int l = 1; l < N; ++l){
63
        int r = l + N - 1;
64
        if(dp[l][r][0] < ansv)ansv = dp[l][r][0], curp = {l, r, 0};
65
        if(dp[l][r][1] < ansv)ansv = dp[l][r][1], curp = {l, r, 1};
66
    }
67
    basic_string < int > rans;
68
    auto [l, r, k] = curp;
69
    auto lst = curp; curp = frm[l][r][k];
70
    while(get < 0 >(curp)){
71
        auto [l, r, k] = lst;
72
        auto [cl, cr, ck] = curp;
73
        if(l != cl)rans += l;
74
        else rans += r;
75
        lst = curp;
76
        curp = frm[cl][cr][ck];
77
    }rans += get < 0 >(lst);
78
    for_each(rans.rbegin(), rans.rend(), [rans](auto val)->void{printf("%d%c", val > N ? val - N : val, val == *prev(rans.rend()) ? '\n' : ' ');});
79
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
80
    return 0;
81
}
82

83
template < typename T >
84
inline T read(void){
85
    T ret(0);
86
    int flag(1);
87
    char c = getchar();
88
    while(c != '-' && !isdigit(c))c = getchar();
89
    if(c == '-')flag = -1, c = getchar();
90
    while(isdigit(c)){
91
        ret *= 10;
92
        ret += int(c - '0');
93
        c = getchar();
94
    }
95
    ret *= flag;
96
    return ret;
97
}

UPD

update-2023_03_06 初稿