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 dp[MAX_N][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(dp, 0x3f, sizeof(dp));
- for (int i = 1; i <= N; i++) {
- if (cows[i] == 0)
- dp[0][i][0] = 0;
- }
- for (int len = 1; len < N; len++) { // 1 ... original N
- int ccount = N - len; // cow count
- for (int i = 1; i + len <= N + 1; i++) {
- dp[len][i - 1][0] = min(dp[len][i - 1][0], dp[len - 1][i][0] + ccount * (cows[i] - cows[i - 1]));
- dp[len][i - 1][0] = min(dp[len][i - 1][0], dp[len - 1][i][1] + ccount * (cows[i + len - 1] - cows[i - 1]));
- dp[len][i][1] = min(dp[len][i][1], dp[len - 1][i][0] + ccount * (cows[i + len] - cows[i]));
- dp[len][i][1] = min(dp[len][i][1], dp[len - 1][i][1] + ccount * (cows[i + len] - cows[i + len - 1]));
- }
- }
- cout << min(dp[N-1][1][0], dp[N-1][1][1]) << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
