POJ 3255 / 12222 Mountain Road：DP+貪心調度單車道雙向交通

問題建模

單車道山路，A/B 兩端各有車隊。每車含方向、到達時間、通行時間。約束：

1. 路中不能有反向車。
2. 同向車間隔 ≥ 10 秒；若中間穿插反向車，則不受 10 秒限制。

目標：安排通行順序，使最後一輛車離開時間最早。

貪心性質

同方向車隊中，到達時間早的車**必定優先通行**（否則只會增加等待）。輸入已按到達時間升序，無需排序。

動態規劃狀態

dp[i][j][d]：前 i 輛 A 向車、j 輛 B 向車已通行，最後一輛車方向為 d（0=A, 1=B）的最早完成時間。

轉移：從 dp[i][j][0] 可連續派遣 k 輛 B 向車（k≥1），計算其完成時間更新 dp[i][j+k][1]；反之亦然。

關鍵計算邏輯

派遣一批同向車時，維護 start_time（批次首車實際進入時間）與 end_time（批次尾車離開時間）：

start = max(dp[i][j][opposite], car.arrival);
end = max(start + car.time, end); // 考慮前車未離開
dp[new_i][new_j][dir] = min(dp[new_i][new_j][dir], end);
start += 10; end += 10; // 同向間隔 10 秒

完整 C 代碼

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MAXN 205

struct Car { int arrival, time; } A[MAXN], B[MAXN];
int dp[MAXN][MAXN][2];
int n, a_cnt, b_cnt;

int solve() {
    memset(dp, INF, sizeof(dp));
    dp[0][0][0] = dp[0][0][1] = 0;
    for (int i = 0; i <= a_cnt; ++i) {
        for (int j = 0; j <= b_cnt; ++j) {
            // 從 A 方向轉 B 方向
            int s = dp[i][j][0], end = 0;
            for (int k = j+1; k <= b_cnt; ++k) {
                s = max(s, B[k].arrival);
                end = max(s + B[k].time, end);
                dp[i][k][1] = min(dp[i][k][1], end);
                s += 10; end += 10;
            }
            // 從 B 方向轉 A 方向
            s = dp[i][j][1]; end = 0;
            for (int k = i+1; k <= a_cnt; ++k) {
                s = max(s, A[k].arrival);
                end = max(s + A[k].time, end);
                dp[k][j][0] = min(dp[k][j][0], end);
                s += 10; end += 10;
            }
        }
    }
    return min(dp[a_cnt][b_cnt][0], dp[a_cnt][b_cnt][1]);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        a_cnt = b_cnt = 0;
        for (int i = 0; i < n; ++i) {
            char dir[2]; int t, d;
            scanf("%s%d%d", dir, &t, &d);
            if (dir[0] == 'A') A[++a_cnt] = {t, d};
            else B[++b_cnt] = {t, d};
        }
        printf("%d\n", solve());
    }
    return 0;
}

複雜度

• 時間：O(n³)（n≤200 可接受）。
• 空間：O(n²)。