Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAX_N = 1005;
- int N;
- int cows[MAX_N];
- int best[MAX_N][2], best2[MAX_N][2];
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- freopen("cowrun.in", "r", stdin);
- freopen("cowrun.out", "w", stdout);
- cin >> N;
- for (int i = 1; i <= N; i++) {
- cin >> cows[i];
- }
- N += 1;
- cows[N] = 0;
- sort(cows + 1, cows + N + 1);
- memset(best, 0x3f, sizeof(best));
- for (int i = 1; i <= N; i++) {
- if (cows[i] == 0)
- best[i][0] = 0;
- }
- for (int len = 1; len < N; len++) { // 1 ... original N
- int ccount = N - len; // cow count
- memset(best2, 0x3f, sizeof(best2));
- for (int i = 1; i + len <= N + 1; i++) {
- best2[i - 1][0] = min(best2[i - 1][0], best[i][0] + ccount * (cows[i] - cows[i - 1]));
- best2[i - 1][0] = min(best2[i - 1][0], best[i][1] + ccount * (cows[i + len - 1] - cows[i - 1]));
- best2[i][1] = min(best2[i][1], best[i][0] + ccount * (cows[i + len] - cows[i]));
- best2[i][1] = min(best2[i][1], best[i][1] + ccount * (cows[i + len] - cows[i + len - 1]));
- }
- memcpy(best, best2, sizeof(best));
- }
- cout << min(best[1][0], best[1][1]) << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
