poj 3616 Milking Time

原题地址

知识点：权值区间DP

解题报告

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct P {
  int start, end, e;
};

bool cmp(const P &a, const P &b) {
  return a.start < b.start;
}

int N, M, R;
struct P a[1002];
int dp[1002];

int main() {
  scanf("%d %d %d", &N, &M, &R);
  int i, j;
  for(i=0;i<M;i++) {
    struct P p;
    scanf("%d %d %d", &p.start, &p.end, &p.e);
    // 化成带权值的区间 DP
    p.end += R;
    a[i] = p;
  }

  sort(a, a+M, cmp);
  for(i=0;i<M;++i) {
    dp[i] = a[i].e;
    for(j=0;j<i;++j) {
      // 把当前时间段允许的之前的时间段都选一遍并取最大值
      if (a[j].end <= a[i].start) dp[i] = max(dp[i], dp[j]+a[i].e);
    }
  }

  cout << *max_element(dp, dp+M) << endl;
  return 0;
}