改对了是我活爹 95pts WA #15

// Problem: P9119 [春季测试 2023] 圣诞树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9119
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const long double INF = 9e18;
struct Node
{
	int x,y,id;
}fat[1005][1005][2],st;
int n,cnt1,cnt2,lef[1005],rig[1005],idtop=1e9;
long double x[1005],y[1005],f[1005][1005][2],maxy=-1e18;
long double answ=9e18;
long double disq(int a,int b)
{
	return sqrt(1.0*abs(x[a]-x[b])*abs(x[a]-x[b])+1.0*abs(y[a]-y[b])*abs(y[a]-y[b]));
}
void dfs(int xx,int yy,int id)
{
	if ((!xx)&&(!yy))
	{
		cout<<idtop<<' ';
		return;
	}
	dfs(fat[xx][yy][id].x,fat[xx][yy][id].y,fat[xx][yy][id].id);
	if (id==0)
	{
		cout<<lef[xx]<<' ';
	}
	else
	{
		cout<<rig[yy]<<' ';
	}
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		if (y[i]>maxy||(y[i]==maxy&&x[i]<x[idtop]))
		{
			maxy=y[i];
			idtop=i;
		}
	}
	for (int i=idtop-1;i>=1;i--)
	{
		cnt1++;
		lef[cnt1]=i;
	}
	for (int i=n;i>=idtop+1;i--)
	{
		cnt1++;
		lef[cnt1]=i;
	}
	for (int i=idtop+1;i<=n;i++)
	{
		cnt2++;
		rig[cnt2]=i;
	}
	for (int i=1;i<=idtop-1;i++)
	{
		cnt2++;
		rig[cnt2]=i;
	}
	lef[0]=idtop,rig[0]=idtop;
	for (int i=0;i<=1000;i++){for (int j=0;j<=1000;j++) f[i][j][0]=f[i][j][1]=1e9;}
	f[0][0][0]=f[0][0][1]=0;
	for (int i=1;i<=n-1;i++)
	{
		for (int j=0;j<=i;j++)
		{
			int leff=j,rigg=i-j;
			if (leff>=1) 
			{
				long double tmp1=f[leff-1][rigg][0]+disq(lef[leff-1],lef[leff]);
				long double tmp2=f[leff-1][rigg][1]+disq(rig[rigg],lef[leff]);
				if (tmp1<=tmp2)
				{
					fat[leff][rigg][0]={leff-1,rigg,0};
				}
				else
				{
					fat[leff][rigg][0]={leff-1,rigg,1};
				}
				f[leff][rigg][0]=min(tmp1,tmp2);
			}
			if (rigg>=1) 
			{
				long double tmp1=f[leff][rigg-1][1]+disq(rig[rigg-1],rig[rigg]);
				long double tmp2=f[leff][rigg-1][0]+disq(lef[leff],rig[rigg]);
				if (tmp1<=tmp2)
				{
					fat[leff][rigg][1]={leff,rigg-1,1};
				}
				else
				{
					fat[leff][rigg][1]={leff,rigg-1,0};
				}
				f[leff][rigg][1]=min(tmp1,tmp2);
			}
		}
	}
	for (int i=0;i<=n-1;i++)
	{
		int gett1=i,gett2=n-i-1;
		if (answ>f[gett1][gett2][0])
		{
			answ=f[gett1][gett2][0];
			st={gett1,gett2,0};
		}
		if (answ>f[gett1][gett2][1])
		{
			answ=f[gett1][gett2][1];
			st={gett1,gett2,1};
		}
	}
	dfs(st.x,st.y,st.id);
	return 0;
}