PKU 3616 - Milking Time
問題文 : Milking Time
解法 :
dp[N] : 時間Nまでに得られるミルクの最大量, とすると,
dp[N] = max(i = 1 ... M, e[i] ≦ N | dp[s[i]] + v[i] where s[i] = i番目の仕事が始まる時間, e[i] = i番目の仕事が終わる時間)
となる.
ここで, 区間の端以外の時間はいらないので座標圧縮を行っておく. これでO(M^2)で解を求めることができる.
コード :
#include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <vector> using namespace std; int n, m, r; int s[1024], e[1024], v[1024]; int memo[2048]; int f(int en) { int ret = 0; if (en == 0) return (0); if (memo[en] >= 0) return (memo[en]); for (int i = 0; i < m; i++){ if (e[i] <= en){ ret = max(ret, v[i] + f(s[i])); } } return (memo[en] = ret); } int main() { map<int, int> conv; vector<int> xs; scanf("%d %d %d", &n, &m, &r); n += r; xs.push_back(0); xs.push_back(n); for (int i = 0; i < m; i++){ scanf("%d %d %d", s + i, e + i, v + i); e[i] += r; xs.push_back(s[i]); xs.push_back(e[i]); } sort(xs.begin(), xs.end()); int idx = 0; conv[xs[0]] = idx++; for (int i = 1; i < xs.size(); i++) if (xs[i] != xs[i - 1]) conv[xs[i]] = idx++; for (int i = 0; i < m; i++){ s[i] = conv[s[i]]; e[i] = conv[e[i]]; } n = conv[n]; memset(memo, -1, sizeof(memo)); printf("%d\n", f(n)); return (0); }