11555 - Aspen Avenue

[Ron]

My code complexity is O ( N ) , giving WA.

any idea please..

[SerailHydra]

My solution is DP, and runs O(N^2)

[crackerwang]

My solution is DP, and runs O(N^2)

can U tell me more details?
I do not know how to dp.
THX

[ptargino]

I can't understand what is wrong with my code. I'm getting WA. Could anyone help me?

Code: Select all

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

using namespace std;

double min(double a, double b) {
	return a < b ? a : b;
}

double abs(double a) {
	return a < 0 ? -a : a;
}

double pow(double a) {
	return a * a;
}

int main() {
	int n, l, w, i, leftPlaced, rightPlaced, intervals;
	int pos[2000];
	double best, ly, ry, ldist, rdist;
	double dp[1001], old[1001];
	while (scanf("%d", &n) == 1) {
		scanf("%d%d", &l, &w);
		for (i = 0; i < n; i++)
			scanf("%d", &pos[i]);
		sort(pos, pos + n);
		intervals = (n / 2) - 1;
		for (i = n - 1; i >= 0; i--) {
			copy(dp, dp + n, old);
			for (leftPlaced = 0, rightPlaced = i - leftPlaced; leftPlaced <= i; leftPlaced++, rightPlaced--) {
				if (leftPlaced > n / 2 || rightPlaced > n / 2)
					continue;
				best = -1;
				if (leftPlaced + 1 <= n / 2) {
					ly = (double) leftPlaced / intervals * l;
					ldist = abs(pos[i] - ly);
					best = ldist + old[leftPlaced + 1];
				}
				if (rightPlaced + 1 <= n / 2) {
					ry = (double) rightPlaced / intervals * l;
					rdist = sqrt(pow(w) + pow(pos[i] - ry));
					best = (best < 0) ? rdist + old[leftPlaced] : min(best, rdist + old[leftPlaced]);
				}
				dp[leftPlaced] = best;
			}
		}
		printf("%.10lf\n", dp[0]);
	}
}

[Jan]

Don't miss return 0 in main().

Check the case.

Input:

Code: Select all

6
18467 15
8032
701
15724
11478
10890
8494

Output:

Code: Select all

20861.0980160517

[mf]

Don't miss return 0 in main().

Actually, it's OK to omit return 0 in main() in C++ programs (but not in C).
ISO C++ standard requires that compilers automatically insert 'return 0;' at the end of main().

[SerailHydra]

My solution is DP, and runs O(N^2)

can U tell me more details?
I do not know how to dp.
THX

When we have arranged the first i trees on the left side and j trees on the right side, we use F[j] to denote the minimum distance these trees need to be moved.

It should be easy for you to write the equation.