Problem Link

Luogu P2904 [USACO08MAR] River Crossing S

Approach 1: Copmlete Knapsack DP

First, observe the problem constraints. We need to transport all (n) cows across the river, minimizing the total time. Suppose we make (k) trips, and on the (i)-th trip we take (a_i) cows. Then (a_1 + a_2 + \dots + a_k = n). This can be viewed as having (n) items, where the (i)-th item represents taking (i) cows in one trip. The cost (in terms of cows) is (i), and the value (time) is (2M + M_1 + M_2 + \dots + M_i), which is the crossing time plus the return time (except the last trip where John does not need to return).

Let (dp[j]) be the minimum time to transport (j) cows across the river, including the time for John to row back after each trip. Since we can take any number of cows on each trip, this is a compltee knapsack problem. The recurrence is:

[s_i = s_{i-1} + M_i] [dp[j] = \min(dp[j], dp[j-i] + s_i + 2M)]

Where (s_i) is the prefix sum of rowing times with cows. The answer is (dp[n] - M) because the final trip does not require returning.

The code below implements this with (O(n^2)) complexity.

#include <bits/stdc++.h>
using namespace std;

const int N = 2505;
int n, m;
int a[N], s[N], dp[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            dp[j] = min(dp[j], dp[j - i] + s[i] + 2 * m);
        }
    }
    printf("%d\n", dp[n] - m);
    return 0;
}

Approach 2: Interval DP

Another perspective: suppose we have (x) cows to cross together (with (x > 1)). Instead of taking all at once, we can split them into two groups: first (y) cows and then the remaining (x-y) cows. Let (dp[i]) be the minimum time to transport (i) cows. If we do not split, the time is (dp[x]). If we split, we solve two subproblems of sizes (y) and (x-y), and then add the time for the empty boat to return after the first group (which is (M)). Thus:

[dp[i] = \min\left(dp[i], dp[j] + dp[i-j] + M\right)]

The initialization is: [dp[0] = M] [dp[i] = dp[i-1] + M_i \quad (i \ge 1)]

This is equivalent to the trivial case of taking all cows in one trip. The answer is (dp[n]). The code runs in (O(n^2)).

#include <bits/stdc++.h>
using namespace std;

const int N = 2505;
int n, m;
int a[N], dp[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    dp[0] = m;
    for (int i = 1; i <= n; ++i) dp[i] = dp[i - 1] + a[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            dp[i] = min(dp[i], dp[j] + dp[i - j] + m);
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}