Submission #58665913

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <math.h>
#define INF 1e300
int N;
int X[11234], Y[11234];
double memo[11234][32];
char memo_valid[11234][32];
double calc(int pos, int skipped) {
  double ans = INF;
  int i;
  if (pos >= N - 1) {
    return skipped > 0 ? pow(2, skipped - 1) : 0;
  }
  if (skipped >= 32) {
    return INF;
  }
  if (memo_valid[pos][skipped]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <math.h>

#define INF 1e300

int N;
int X[11234], Y[11234];

double memo[11234][32];
char memo_valid[11234][32];

double calc(int pos, int skipped) {
	double ans = INF;
	int i;
	if (pos >= N - 1) {
		return skipped > 0 ? pow(2, skipped - 1) : 0;
	}
	if (skipped >= 32) {
		return INF;
	}
	if (memo_valid[pos][skipped]) {
		return memo[pos][skipped];
	}
	for (i = 0; i < 32 && pos + i < N; i++) {
		int next = pos + 1 + i;
		double candidate = calc(next, skipped + i);
		candidate += sqrt((double)(X[next] - X[pos]) * (X[next] - X[pos]) + (double)(Y[next] - Y[pos]) * (Y[next] - Y[pos]));
		if (candidate < ans) ans = candidate;
	}
	memo[pos][skipped] = ans;
	memo_valid[pos][skipped] = 1;
	return ans;
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &X[i], &Y[i]) != 2) return 1;
	}
	printf("%.30f\n", calc(0, 0));
	return 0;
}

Submission Info

Judge Result