The conditions are specified in a somewhat 'interesting' manner. It would be equivalent to say that
From that it is clear that the inter-cow distances must be the floor and ceiling of L / (N - 1). Some simple arithmetic will then give you the number of each gap size to obtain the total length of L.
At this point it is very tempting to use a greedy solution; that is, place each cow in turn as close to its original position as possible while still making it possible to meet the conditions (indeed it was so tempting that some of the coaches fell into the trap). Unfortunately, the greedy algorithm turns out to make local optimisations at the expense of global optimisation. An example of this would be the initial arrangement
1 2 - - - 3 4 5
There will be one 1-step jump and three 2-step jumps, and the optimal arrangement (with total cost 2) is
1 - 2 - 3 - 4 5
However, a greedy algorithm would immediately place cow 2 in the same place as it started, forcing the arrangement (with total cost 3)
1 2 - 3 - 4 - 5
The correct solution is to use dynamic programming (if you don't know what dynamic programming is, look it up in an algorithms textbook or on the web, e.g., at http://people.cs.uct.ac.za/~bmerry/manual/algorithms/dp.html).
For each cow, there is a range of places in which it could be: the first cow must be at position 0, the second cow could be at position D or D + 1, and so on (the constraints are that it must be possible to fit in the other cows on either side using steps of D or D + 1). For each position of each cow, we can work out the minimum cost of placing that cow and all the cows to the left of it. If f(c, p) is the minimum cost of placing cows 1..c with cow c at point p, then
f(1, 0) = start(1) f(c, p) = |start(c) - p| + min(f(c - 1, p - D), f(c - 1, p - D - 1))where D and D + 1 are the legal inter-cow distances. In some cases one of the expressions inside the min will put a cow at an illegal point (in that the other cows cannot be fitted around it); in this case one just takes the other expression.
The memory requirement is only linear, since row c can be computed from row c - 1, after which row c - 1 can be discarded. The run-time efficiency is O(N2).
#include <fstream> #include <algorithm> #include <iterator> #include <vector> #include <utility> using namespace std; static pair<int, int> dp_range(int x, int N, int L, int D) { int lleft = x * D; int hleft = x * (D + 1); int lright = L - (N - 1 - x) * (D + 1); int hright = L - (N - 1 - x) * D; return make_pair(max(lleft, lright), min(hleft, hright)); } int main() { ifstream in("graze1.in"); ofstream out("graze1.out"); vector<int> start; vector<int> dp, old; int N, L, D; in >> N >> L; D = L / (N - 1); start.resize(N); for (int i = 0; i < N; i++) in >> start[i]; if (N == 1) { out << "0\n"; return 0; } dp.resize(L + 1); old.resize(L + 1); dp[0] = start[0]; for (int i = 1; i < N; i++) { swap(dp, old); pair<int, int> oldr = dp_range(i - 1, N, L, D); pair<int, int> r = dp_range(i, N, L, D); for (int j = r.first; j <= r.second; j++) { dp[j] = INT_MAX; if (j - (D + 1) >= oldr.first) dp[j] = min(dp[j], old[j - (D + 1)]); if (j - D <= oldr.second) dp[j] = min(dp[j], old[j - D]); dp[j] += abs(start[i] - j); } } out << dp[L] << "\n"; return 0; }