読者です 読者をやめる 読者になる 読者になる

PKU 3616 Milking Time

3616 -- Milking Time
DP苦手すぎるなあ
はじめから終わる時間+休憩時間にその区間が終わるとみなすと楽かも(ほとんど同じ)
ifdefとか試しに使ってみた

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#undef DEBUG
struct WORK{
    int s, e, c;
    bool operator < (WORK a)const{ return s < a.s;}
} w[1000];
int n, m, r;
int dp[1000];
priority_queue<int> ans;
int main(){
    scanf("%d %d %d", &n, &m, &r);
    for(int i = 0; i < m; i++){
	int tmp;
	scanf("%d %d %d", &w[i].s, &tmp, &w[i].c);
	w[i].e = tmp + r;
    }
    sort(w, w + m);
    for(int i = 0; i < m; i++){
	for(int j = 0; j < i; j++) if(w[i].s >= w[j].e) dp[i] = max(dp[j], dp[i]);
	dp[i] += w[i].c;
	ans.push(dp[i]);
    }
    printf("%d\n", ans.top());
#ifdef DEBUG
    for(int i = 0; i < m; i++){
	printf("%d\n", dp[i]);
    }
#endif
    return 0;
}