mayoko’s diary

プロコンとかいろいろ。

POJ 3616 Milking Time

dp の練習で蟻本のやつを解いてみました。これは簡単。

解法

まずスタートの時間ごとにソートする。

dp[m] = (m 番目から最後までの milking time だけで最大化しようとした場合の最大値)として, 適当に dp する。

struct Milk {
    int start;
    int end;
    int eff;
    Milk() {}
    Milk(int s, int end, int eff) : start(s), end(end), eff(eff) {}
    bool operator<(const Milk& rhs) {
        return start < rhs.start;
    }
};

Milk milk[1024];
int dp[1024];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, R;
    cin >> N >> M >> R;
    for (int i = 0; i < M; i++) {
        cin >> milk[i].start >> milk[i].end >> milk[i].eff;
    }
    sort(milk, milk+M);
    for (int i = M-1; i >= 0; i--) {
        if (i < M-1) dp[i] = dp[i+1];
        int plus = milk[i].eff;
        int t = milk[i].end + R;
        int j;
        for (j = i+1; j < M; j++) {
            if (milk[j].start >= t) break;
        }
        plus += dp[j];
        dp[i] = max(dp[i], plus);
    }
    cout << dp[0] << endl;
    return 0;
}