COLOCON -Colopl programming contest 2018- D すぬけそだて――トレーニング――
この程度の愚直DPが間違ってたのダメ
問題文
- スタミナとよばれる概念があり，0で空，Xで満タンである．時刻1単位でスタミナは1回復する
- 時刻0にてスタミナはXである
- T_1..T_NからK個のタイミングを選んで，スタミナを0にして，スタミナを減らした分だけ経験値がたまる
- 全てのK∈1..Nについて，獲得できる経験値の最大値を計算する．
AC
間違ってたDP
DP[i][j] = 今時刻iを見ていて，j個のタイミングを選んだときの，pair<経験値, -最後に選んだ時刻>
間違っているので説明しませんが，DPテーブルにpairぶち込む時点で怪しんだ方が良さそう．
正しいDP
pdf解説とほぼ同じなので…．
DP[i][j] = 最後に選んだ時刻i，j個のタイミングを選んだときの獲得可能な経験値の最大値
テーブル全体をN回走査する感じになる．
計算量はO(N3)なので，改善する必要がある．
repeat(i, N) { // pointer
repeat(j, i) { // lastindex
repeat(k, i + 1) { // usedcnt
chmax(dp[i][k + 1], dp[j][k] + min(T[i] - T[j], X));
}
}
}
min(T[i] - T[j], X) に注目．
もし，時刻のインデックスを表す変数j1，j2，j1<j2 があって，
X == min(T[i] - T[j1], X) == min(T[i] - T[j2], X) を満たすならば，j2のDP更新は必要無い（スタミナが最大値溜まっているならば，早く使ったほうが最善だから）．
もし，時刻のインデックスを表す変数j1，j2，j1<j2 があって，
X > min(T[i] - T[j1], X) > min(T[i] - T[j2], X) を満たすならば，j1のDP更新は必要無い（スタミナが最大値溜まっていないならば，遅く使ったほうが最善だから？）*1．
ここで，backi[i] = (T[j] + X > T[i] を満たす最小のインデックスj，j<i．)という配列を定義する*2．
こんな感じで求められる
int lasti = 0, lastv = 0; repeat(i, N) { while (lastv + X <= T[i] && lasti < N-1) { lastv = T[++lasti]; } backi[i] = lasti; }
DP遷移をbackiと先ほどの考察を使って改善すると
repeat(i, N) { // pointer
{ // lastindex
const j = back[i];
repeat(k, i + 1) { // usedcnt
chmax(dp[i][k + 1], dp[j][k] + min(T[i] - T[j], X));
}
}
if (back[i] > 0){ // lastindex
const j = back[i]-1;
repeat(k, i + 1) { // usedcnt
chmax(dp[i][k + 1], dp[j][k] + min(T[i] - T[j], X));
}
}
}
answer
セグメント木が貼ってありますが使ってないです
おまけ
backiを計算しながら答えも更新しつつDP
int lasti = 0, lastv = 0; best[0] = X; repeat(i, N) { // pointer while (lastv + X <= T[i] && lasti < N-1) { ++lasti; lastv = T[lasti]; } dp[i][1] = X; const int j = lasti; // lastindex iterate(k, 1, i + 1) { // usedcnt chmax(dp[i][k + 1], max(dp[i][k], dp[j][k] + min(T[i] - T[j], X))); if (j > 0) chmax(dp[i][k + 1], max(dp[i][k], dp[j-1][k] + min(T[i] - T[j-1], X))); chmax(best[k], dp[i][k + 1]); } }
DPループの入れ子を置き換えてみると，空間計算量O(N)のDPが出来る．答えもループ中で確定するので，best[N]も必要ない．
ただし，時間計算量は2倍になっている．
fill(dp, dp+N, X);
iterate(k, 1, N) { // usedcnt
int best = 0;
rrepeat(i, N) { // pointer
const int j = backi[i]; // lastindex
chmax(dp[i], dp[j] + min(T[i] - T[j], X));
if (j > 0)
chmax(dp[i], dp[j-1] + min(T[i] - T[j-1], X));
chmax(best, dp[i]);
}
printer << best << '\n';
}
