POJ 3616 Milking Time：區間 DP + 記憶化搜索

POJ 3616 Milking Time：區間 DP + 記憶化搜索

貝西有 N 小時，農夫約翰提供 M 個擠奶區間 [l_i, r_i)，效率 eff_i。任選區間，但任意兩個選中區間需間隔至少 R 小時。最大化總產奶量。

建模為 DAG 最長路徑

• 每個區間視為一個節點，權值為 eff_i。
• 若區間 i 結束後休息 R 小時可開始區間 j（即 r_i + R ≤ l_j），添加有向邊 i → j。
• 問題轉化為：在 DAG 中找最大權路徑和。

記憶化 DFS 求最長路徑

int dfs(int u) {
    if (dp[u]) return dp[u];
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        dp[u] = max(dp[u], dfs(v));
    }
    dp[u] += w[u];
    return dp[u];
}

• dp[u] 存儲從節點 u 出發的最大收益。
• 拓撲序天然由時間順序保證，無環。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
struct Interval { int l, r, eff; } iv[N];
int head[N], to[N*N], nxt[N*N], ecnt;
int dp[N], w[N];

void addEdge(int u, int v) {
    to[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++;
}

int dfs(int u) {
    if (dp[u]) return dp[u];
    for (int i = head[u]; ~i; i = nxt[i])
        dp[u] = max(dp[u], dfs(to[i]));
    return dp[u] += w[u];
}

int main() {
    int n, m, R;
    while (~scanf("%d%d%d", &n, &m, &R)) {
        memset(head, -1, sizeof(head));
        memset(dp, 0, sizeof(dp));
        ecnt = 0;
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &iv[i].l, &iv[i].r, &iv[i].eff);
            w[i] = iv[i].eff;
        }
        for (int i = 1; i <= m; ++i)
            for (int j = i+1; j <= m; ++j) {
                if (iv[i].r + R <= iv[j].l) addEdge(i, j);
                else if (iv[j].r + R <= iv[i].l) addEdge(j, i);
            }
        int ans = 0;
        for (int i = 1; i <= m; ++i) ans = max(ans, dfs(i));
        printf("%d\n", ans);
    }
    return 0;
}

複雜度 O(M²) 建圖 + O(M) DP，M ≤ 1000 完全足夠。