RT,错误原因为输出0

评测记录

#include<bits/stdc++.h>
using namespace std;
long double dp[2010][2010][2];
long double x[2010], y[2010];
int n, k, pre[2010][2010][2];
long double d(int i, int j) {
	return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
void write(int l, int r, int k) {
	if (l == 0 || r == 0) {
		cout << k << " ";
		return;
	}
	if (l >= r) {
		cout << (l - n <= 0 ? l : l - n) << " ";
		return;
	} else if (k) {
		write(l, r - 1, pre[l][r][k]);
		cout << (r - n <= 0 ? r : r - n) << " ";
	} else {
		write(l + 1, r, pre[l][r][k]);
		cout << (l - n <= 0 ? l : l - n) << " ";
	}
}
signed main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> x[i] >> y[i];
	for (int i = 1; i <= n; i++) {
		if (y[i] > y[k])k = i;
		x[i + n] = x[i];
		y[i + n] = y[i];
	}
	for (int i = 0; i <= 2 * n; i++) {
		for (int j = 0; j <= 2 * n; j++) {
			dp[i][j][0] = dp[i][j][1] = 1e9;
		}
	}
	dp[k][k][0] = dp[k][k][1] = 0;
	dp[k + n][k + n][0] = dp[k + n][k + n][1] = 0;
	for (int l = 2; l <= n; l++) {
		for (int i = 1; i + l - 1 <= 2 * n; i++) {
			int j = i + l - 1;
			if (j < k || i > k)continue;
			dp[i][j][1] = min(dp[i][j][1], min(dp[i][j - 1][1] + d(j - 1, j), dp[i][j - 1][0] + d(i, j)));
			if (dp[i][j][1] == dp[i][j - 1][1] + d(j - 1, j))pre[i][j][1] = 1;
			else pre[i][j][1] = 0;
			dp[i][j][0] = min(dp[i][j][0], min(dp[i + 1][j][1] + d(j, i), dp[i + 1][j][0] + d(i + 1, i)));
			if (dp[i][j][0] == dp[i + 1][j][1] + d(j, i))pre[i][j][0] = 1;
			else pre[i][j][0] = 0;
		}
	}
	int l = 0, r = 0, k = 0;
	for (int i = 1; i <= n; i++) {
		int j = i + n - 1;
		if (dp[i][j][0] < dp[l][r][k]) {
			l = i;
			r = j;
			k = 0;
		}
		if (dp[i][j][1] < dp[l][r][k]) {
			l = i;
			r = j;
			k = 1;
		}
	}
	//cout<<dp[l][r][k]<<"\n";
	write(l, r, k);
	return 0;
}