T2-7 River Crossing

题意理解

约翰要用木筏把 $N$ 头奶牛运过河。运 $k$ 头牛单程需要 $M + M_1 + M_2 + \cdots + M_k$ 分钟。每批运完后（除最后一批外）约翰要空船返回，返回需要 $M$ 分钟。求最少总时间。

---

思路分析

使用动态规划。

先预处理 $cost[k]$ 表示一次运 $k$ 头牛过河的单程时间：

$$cost[k] = M + M_1 + M_2 + \cdots + M_k$$

设 $dp[i]$ 表示：运完前 $i$ 头牛并返回原岸的最小时间。

状态转移：

枚举这一批运多少头牛：

$$dp[i] = min_{j=0}^{i-1}(dp[j] + cost[i-j] + M)$$

边界条件：

• $dp[0] = 0$：没有牛需要运送

答案： $dp[N] - M$（最后一批不需要返回）

---

参考代码

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

const int MAXN = 2505;  // 最大奶牛数量

int n, M;           // 奶牛数量和空船过河时间
int m[MAXN];        // m[i]表示多载一头牛增加的时间
int cost[MAXN];     // cost[k]表示一次运k头牛的单程时间
int dp[MAXN];       // dp[i]表示运完前i头牛并返回的最小时间

int main() {
    cin >> n >> M;  // 读入奶牛数量和空船时间
    
    for (int i = 1; i <= n; i++) {  // 读入每增加一头牛的额外时间
        cin >> m[i];
    }
    
    cost[0] = M;  // 运0头牛就是空船时间
    for (int i = 1; i <= n; i++) {  // 预处理运i头牛的单程时间
        cost[i] = cost[i - 1] + m[i];
    }
    
    memset(dp, 0x3f, sizeof(dp));  // 初始化为无穷大
    dp[0] = 0;  // 边界：没有牛需要运送
    
    for (int i = 1; i <= n; i++) {  // 枚举前i头牛
        for (int j = 0; j < i; j++) {  // 枚举上一批运完后的状态
            dp[i] = min(dp[i], dp[j] + cost[i - j] + M);  // 这一批运第j+1到第i头牛，然后返回
        }
    }
    
    cout << dp[n] - M << endl;  // 答案减去最后一批的返回时间
    return 0;
}