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

Tsawke · 2023-03-09 20:41:17 · 题解

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

[TOC]

更好的阅读体验戳此进入

游记戳此进入

题面

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

Solution

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

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

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

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N;
pair < ld, ld > pts[2100];
ld dis[2100][2100];
ld dp[2100][2100][2];
tuple < int, int, int > frm[2100][2100][2];
int top(-1); ld topy(-1e8);

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

    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;
    N = read();
    for(int i = 1; i <= N; ++i){
        scanf("%Lf%Lf", &pts[i].first, &pts[i].second);
        pts[i + N] = pts[i];
        if(pts[i].second > topy)topy = pts[i].second, top = i;
    }
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)
        dis[i][j] = dis[i + N][j] = dis[i][j + N] = dis[i + N][j + N] = CalDis(pts[i], pts[j]);
    dp[top][top][0] = dp[top][top][1] = dp[top + N][top + N][0] = dp[top + N][top + N][1] = 0.0;
    for(int len = 2; len <= N; ++len)
        for(int l = 1; l <= (N << 1) - len + 1; ++l){
            int r = l + len - 1;
            Update(l, r, 0, l + 1, r, 0, l + 1, l);
            Update(l, r, 0, l + 1, r, 1, r, l);
            Update(l, r, 1, l, r - 1, 0, l, r);
            Update(l, r, 1, l, r - 1, 1, r - 1, r);
        }
    ld ansv(1e12); tuple < int, int, int > curp(0, 0, 0);
    for(int l = 1; l < N; ++l){
        int r = l + N - 1;
        if(dp[l][r][0] < ansv)ansv = dp[l][r][0], curp = {l, r, 0};
        if(dp[l][r][1] < ansv)ansv = dp[l][r][1], curp = {l, r, 1};
    }
    basic_string < int > rans;
    auto [l, r, k] = curp;
    auto lst = curp; curp = frm[l][r][k];
    while(get < 0 >(curp)){
        auto [l, r, k] = lst;
        auto [cl, cr, ck] = curp;
        if(l != cl)rans += l;
        else rans += r;
        lst = curp;
        curp = frm[cl][cr][ck];
    }rans += get < 0 >(lst);
    for_each(rans.rbegin(), rans.rend(), [rans](auto val)->void{printf("%d%c", val > N ? val - N : val, val == *prev(rans.rend()) ? '\n' : ' ');});
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_03_06 初稿