P9119 [春季测试 2023] 圣诞树

Rt__ · 2024-11-21 12:01:55 · 题解

P9119 [春季测试 2023] 圣诞树

题意简述

给定一个凸包，求出从最高点开始将这个凸包的所有点走一遍的最小距离。

思路

由图可以发现，我们从一边往下走的时候时不可能再向上，会导致路径更长。

比如：

一定比

路程短。

所以我们可以采取贪心的策略：两边交替向下，路径不相交，直到将整个圆环全部走完为之。所以我们先找到最高点，并记录编号为 k，再由该做法设出：f_{i, j, 0/1} 表示从左边下了 i 步，从右边下了 j 步，目前在左边/右边的最小距离。状态转移方程为（d_{i, j} 记为编号 i,j 两点的欧几里德距离）：

然后我们在转移时把每个位置的前驱记录下来，到最后找到 f_{i, n - 1 - i} 中最小的地方，直接倒序找到转移方案输出即可。

考场错因

我在处理的时候把这个环劈开，变成左右两边，再从左右依次往下走。但事实上他有可能最终的节点不在最底下，所以一直有错误。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define ld long double

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return f * res;
}

const int N = 5010;
const ld INF = 1e9;

ll n, k, la[N][N][2];
ld f[N][N][2];

struct poi{
    ld x, y;
}tr[N];

ld d(int a, int b){
    if(a <= 0)a += n;
    if(b <= 0)b += n;
    if(a > n)a %= n;
    if(b > n)b %= n;
    ld res = sqrt( pow(tr[a]. x - tr[b]. x, 2) + pow(tr[a]. y - tr[b]. y, 2) );
    // cout << a << ' ' << b << ' ' << res << endl;
    return res;
}

int ans[N];

signed main(){
    n = read();
    ld maxx = -INF;
    for(int i = 1; i <= n; i ++){
        cin >> tr[i]. x >> tr[i]. y;
        if(tr[i]. y > maxx){
            k = i;
            maxx = tr[i]. y;
        }
    }

    for(int i = 1; i < n; i ++){
        f[0][i][1] = f[0][i - 1][1] + d(k - (i - 1), k - i);
        la[0][i][1] = 1;
        f[0][i][0] = INF;
        f[i][0][0] = f[i - 1][0][0] + d(k + i, k + (i - 1));
        la[i][0][0] = 0;
        f[i][0][1] = INF;
    }
    for(int i = 1; i < n; i ++){
        for(int j = 1; i + j < n; j ++){
            if(f[i - 1][j][0] + d(k + i, k + (i - 1)) <  f[i - 1][j][1] + d(k + i, k - j)){
                la[i][j][0] = 0;
                f[i][j][0] = f[i - 1][j][0] + d(k + i, k + (i - 1));
            }
            else{
                la[i][j][0] = 1;
                f[i][j][0] = f[i - 1][j][1] + d(k + i, k - j);
            }

            if(f[i][j - 1][1] + d(k - j, k - (j - 1)) < f[i][j - 1][0] + d(k - j, k + i)){
                la[i][j][1] = 1;
                f[i][j][1] = f[i][j - 1][1] + d(k - j, k - (j - 1));
            }
            else{
                la[i][j][1] = 0;
                f[i][j][1] = f[i][j - 1][0] + d(k - j, k + i);
            }
        }
    }
    ld minn = INF;
    int l, r, op;
    for(int i = 0; i < n; i ++){
        if(minn > f[i][n - 1 - i][0]){
            minn = f[i][n - 1 - i][0];
            l = i, r = n - i - 1, op = 0;
        }
        if(minn > f[i][n - 1 - i][1]){
            minn = f[i][n - 1 - i][1];
            l = i, r = n - i - 1, op = 1;
        }
        // cout << i << ' ' << n - i - 1 << ' ' << f[i][n - i - 1][0] << ' ' << f[i][n - i - 1][1] << endl;
    }
    // cout << minn << ' ' << l << ' ' << r << ' ' << op << endl;
    int idx = 0;
    while(l || r){
        int mid;
        if(op)mid = k - r;
        else mid = k + l;
        if(mid > n)mid %= n;
        if(mid <= 0)mid += n;
        ans[++ idx] = mid;
        int mid_l = l, mid_r = r;
        if(op)r --;
        else l --;
        op = la[mid_l][mid_r][op];
    }
    cout << k << ' ';
    for(int i = idx; i >= 1; i --)cout << ans[i] << ' ';
    return 0;
}