Poj 3616: Milking Time

poj3616.md

Poj 3616: Milking Time

題目

分析

想到二維去了…這題用一維 DP 就可以了。

###定義

Let dp[i] = 前 i 個時段中擠牛奶所能得到的最大值，且「必須」使用第 i 個時段

答案不是 dp[M-1]，因最後一個時段不一定會用。答案是 *max_element(dp, dp + M)

###轉移方程式：

dp[i] = max([dp[k] for 0 <= k < i 且 第 k 個時段沒有與第 i 個時間重疊]) 
        + 第 i 個時段的 effeciency

另外，須注意可能會沒有任一個時段有符合重疊的限制，此時

dp[i] = 第 i 個時段的 effeciency

###初使條件

dp[0] = 第 0 個時段的 effeciency。

順序為開始時間早的先做。

AC Code

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

struct Interval {
    int start, end, effeciency;

    bool operator < (const Interval& i) const {
        if (start != i.start)
            return start < i.start;
        return end < i.end;
    }
};

int N, M, R;
Interval data[1000];
int dp[1000];

int solve() {
    sort(data, data + M);

    dp[0] = data[0].effeciency;
    for (int i = 1; i < M; i++) {
        int m = 0;
        for (int j = 0; j < i; j++)
            if (data[j].end + R <= data[i].start)
                m = max(m, dp[j]);
        dp[i] = m + data[i].effeciency;
    }

    return *max_element(dp, dp + M);
}


int main() {
    scanf("%d %d %d", &N, &M, &R);
    for (int i = 0; i < M; i++)
        scanf("%d %d %d", &data[i].start, &data[i].end, &data[i].effeciency);
    printf("%d\n", solve());

    return 0;
}