POJ 2336 Ferry Loading II：貪心與 DP 雙解法深度解析

問題重述

m 輛車需過河，渡船單程 t 時間，容量 n。第 i 輛車到達碼頭時間 time[i]（遞增）。求：
1. 最少航次 2. 最早全員到達時間。

貪心策略與證明

最少航次：trips = ceil(m/n)。若 m%n == 0 則每趟滿載 n 輛；否則首趟載 m%n 輛，其餘滿載。
最早時間：盡早送走最後一批車。貪心決策：每趟盡可能早出發，但必須等待該趟最後一輛車到達。

貪心算法流程

r = m % n;           // 首趟載車數
k = m / n;           // 後續滿載趟數
ansTrips = r ? k+1 : k;

if (r) curTime = time[r] + 2*t;  // 首趟：等第 r 輛車，去+回
else   curTime = time[n] + 2*t;  // 首趟滿載

for (int j = 1; j <= k; ++j) {
    int idx = j*n + r;           // 當前趟最後一輛車索引
    curTime = max(curTime, time[idx]) + 2*t;
    if (j == k) curTime -= t;    // 最後一趟無需返回
}
ansTime = curTime;

動態規劃通用解法

dp[i] = 送走前 i 輛車的最早時間。
num[i] = 對應航次數。
轉移：枚舉上一趟送走 j 輛車 (i-n ≤ j < i)：

for i = 1..m:
    dp[i] = INF
    for j = max(0,i-n) .. i-1:
        depart = max(dp[j] + t, time[i])  // 船返回 vs 車到達
        arrive = depart + t
        if arrive < dp[i] or (arrive==dp[i] and num[j]+1 < num[i]):
            dp[i] = arrive, num[i] = num[j]+1

初始 dp[0] = -t（視為船已在原岸，時間回推 t）。

兩種方法對比

完整代碼（貪心版）

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, t, m; scanf("%d%d%d", &n, &t, &m);
        vector time(m+1);
        for (int i=1;i<=m;++i) scanf("%d", &time[i]);
        
        int r = m % n, k = m / n;
        int trips = r ? k+1 : k;
        long long cur = 0;
        
        if (r) cur = time[r] + 2LL*t;
        else if (m) cur = time[n] + 2LL*t;
        
        for (int j=1; j<=k; ++j) {
            int idx = j*n + r;
            cur = max(cur, (long long)time[idx]) + 2LL*t;
            if (j == k) cur -= t;
        }
        printf("%lld %d\n", cur, trips);
    }
    return 0;
}

關鍵細節

• 用 long long 避免時間累加溢出（m,t ≤ 10^4，累加 ≤ 10^8）。
• dp[0] = -t 技巧：首趟無需等船返回，統一公式。
• 輸入車輛時間已按到達順序給出，無需排序。