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; }