P9119 [春季测试 2023] 圣诞树

题意简述

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

思路

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

比如：

一定比

路程短。

所以我们可以采取贪心的策略：两边交替向下，路径不相交，直到将整个圆环全部走完为之。所以我们先找到最高点，并记录编号为

k

，再由该做法设出：

f_{i, j, 0/1}

表示从左边下了

i

步，从右边下了

j

步，目前在左边/右边的最小距离。状态转移方程为（

d_{i, j}

记为编号

i,j

两点的欧几里德距离）：

f_{i, j, 0} = \max(f_{i - 1, j, 0} + d_{k + i - 1, k + i}，f_{i - 1, j, 1} + d_{k + i, k - j})

f_{i, j, 1} = \max(f_{i, j - 1, 1} + d_{k - (j - 1), k - j}，f_{i, j - 1, 0} + d_{k + i, k - j})

然后我们在转移时把每个位置的前驱记录下来，到最后找到

f_{i, n - 1 - i}

中最小的地方，直接倒序找到转移方案输出即可。

考场错因

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

代码

CPP

#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;
}

P9119 [春季测试 2023] 圣诞树

文章操作

题意简述

思路

考场错因

代码

相关推荐

评论

P9119 [春季测试 2023] 圣诞树