Algoogle

Algorithm for Programming Contest

PKU 3616 Milking Time

Category: PKU Tag: dp

Milking Time

問題概要


解法


dp[i] := i 番目のインターバルをやったときの最大値
とすればそれより前までのやつに足したやつとの最大を取っていけばいい.
終了時刻は入力時に+Rしといて, 開始時刻でソートしておく.
Nはいらない.

コード


(3616.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <cstdio>

using namespace std;

struct S{
    int s, t, e;
    S(){}
    S(int s, int t, int e):s(s),t(t),e(e){}
    bool operator<(const S &a) const{ return s < a.s;}
};

int N, M, R;
S inter[1024];
int dp[1024];

int main(){
    scanf("%d%d%d", &N, &M, &R);
    N += R;
    for(int i = 0; i < M; i++){
        int s, t, e; scanf("%d%d%d", &s, &t, &e);
        inter[i] = S(s,t+R,e);
    }
    sort(inter, inter+M);

    int ans = 0;
    for(int i = 0; i < M; i++){
        dp[i] = inter[i].e;
        for(int j = 0; j < i; j++)
            if(inter[i].s >= inter[j].t)
                dp[i] = max(dp[i], dp[j]+inter[i].e);
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

Comments