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