ZOJ Monthly, September 2012 - J : Sleeper's Schedule
問題概要
N(<1e3)個の重み付き区間がある(区間の座標<=1e4)。今時刻0であなたは目が覚めた。起きている時間tが[T,T+L]に含まれるときあなたは寝ることができる。このときペナルティ(t-T)^2を支払う。寝たらK+(t-T)時間後に再び目を覚ます。最大いくつの重みを獲得できるか求める問題。
解法
dp[t][i] = {時刻tに、i時間連続で起きているときのスコアの最大値}
とするとO( (N+MAX_X)*(T+L) )で解ける。
acceptされたコード
const int MAX_N = 1000; const int MAX_T = 10000; const int MAX_AWAKE = 100 + 20; const int INF = int(1.05e9); int N, T, K, L; vector<pair<int,int> > contests[MAX_T + 1]; //(end, value) int opt[MAX_T + 1][MAX_AWAKE + 1]; void init() { scanf("%d%d%d%d", &N, &T, &K, &L); for (int i = 0; i <= MAX_T; ++i) { contests[i].clear(); } for (int _ = 0; _ < N; ++_) { int from, to, value; scanf("%d%d%d", &from, &to, &value); contests[from].push_back(make_pair(to, value)); } } inline int sq(int x) { return x*x; } int solve() { for (int i = 0; i <= MAX_T; ++i) { fill(opt[i], opt[i] + MAX_AWAKE + 1, -INF); } opt[0][0] = 0; for (int t = 0; t < MAX_T; ++t) { for (int i = 0; i <= T + L; ++i) if (opt[t][i] > -INF) { //コンテストに参加してみる for (int j = 0; j < int(contests[t].size()); ++j) { const int endTime = contests[t][j].first, value = contests[t][j].second; const int dulation = endTime - t; if (i + dulation > T + L) { continue; } int nxtValue = value; nxtValue += (i >= T ? sq(i - T) : 0); nxtValue -= (i + dulation >= T ? sq(i + dulation - T) : 0); updateMax(opt[endTime][i + dulation], opt[t][i] + nxtValue); } //コンテストに参加しない //寝る if (i >= T) { const int nxt = min(MAX_T, t + K + (i - T)); updateMax(opt[nxt][0], opt[t][i]); } //起きる if (i < T + L) { updateMax(opt[t+1][i+1], opt[t][i] - (i >= T ? 2 * (i - T) + 1 : 0)); } } } int ans = 0; for (int i = 0; i <= T + L; ++i) { updateMax(ans, opt[MAX_T][i]); } return ans; }