[Code Formula 2014 本選] D - 映画の連続視聴
[Q] https://atcoder.jp/contests/code-formula-2014-final/tasks/code_formula_2014_final_d
1. DPですが、DP[3000][3000]をエスパー。
2. シンプルに、
DP[今見てる映画]、をいれたら、
DP[今見てる映画][次見る映画]、にしたい。でも連続数も外せない。
DP[今見てる映画][次見る映画][連続数]、これはO(N^3)でダメそう。
3. どうしよう？
A. 次見る映画は、全部見る必要がなさそう。考察する。
Q. 映画 0 から、どの映画に遷移する？
0: 1 1-10
1: 1 10-20
2: 1 100-110
こんな 3 本があったとき、
0->1 はあるけど、
0->2 は絶対にないのがわかる。途中で 1 をみたほうがいい。
Q. 映画 0 から、どの映画に遷移する？
0: 1 1-10
1: 1 10-20
2: 1 100-110
3: 2 10-20
4: 2 100-110
0->1
0->3
の2通りだけ見ればいい。
映画の種類ごとに、好条件なものを1つ見に行けばよさそう
<<< 気を付けないといけないパターンがあった >>>
Q. 映画 0 から、どの映画に遷移する？
0: 1 1-10
1: 1 10-2000
2: 1 100-110
0->2
だけ見る。DP[今の映画][連続数]として、次の映画に進む条件は2つ。
1. 今の映画を見終わったあと、開始に間に合うもの
2. 開始に間に合うもののうち、終了時間が一番早いもの
これを、映画の種類ごとに全部見ていけばいい。
4. DP遷移、どうしよう？
配るDPっぽく実装。
次の遷移先で「遷移先の映画を見た」とする場合の幸福度をvalにいれる。
2パターンに分けられる。
1. 違う種類に移る場合はかんたん。連続数が途切れるので、0だけ。
DP[next][0] = 前の映画の最大スコア + H[0]
前映画の最高値に、連続0回目の幸福度を足せば、次の映画の連続0。
2. 同じ種類に移る場合は、連続数を更新。O(N)
DP[next][1] = DP[pre][0] + H[1]
DP[next][2] = DP[pre][1] + H[2]
DP[next][3] = DP[pre][2] + H[3]
...
遷移の確認
Q. 入力例2
N = 10
H[] = 100 200 250 250 300 400 540 600 650 680
0: 1 10 130
1: 2 0 900
2: 1 20 110
3: 1 200 230
4: 3 200 210
5: 2 201 220
6: 2 240 300
7: 3 0 90
8: 1 250 320
9: 2 330 400
・遷移の仕方
id:7 eiga:2 nid:3
id:7 eiga:2 nid:5
id:7 eiga:2 nid:4
id:0 eiga:0 nid:3
id:0 eiga:0 nid:5
id:0 eiga:0 nid:4
id:2 eiga:0 nid:3
id:2 eiga:0 nid:5
id:2 eiga:0 nid:4
id:3 eiga:0 nid:8
id:3 eiga:0 nid:6
id:4 eiga:2 nid:8
id:4 eiga:2 nid:6
id:5 eiga:1 nid:8
id:5 eiga:1 nid:6
id:6 eiga:1 nid:9
id:8 eiga:0 nid:9
・DP値
DP[0][0]:100 // 0
DP[1][0]:100 // 1
DP[2][0]:100 // 2
DP[3][0]:200 // 7,3
DP[3][1]:300 // 2,3
DP[4][0]:200 // 7,4
DP[4][1]:300 // 7,4
DP[5][0]:200 // 7,5
DP[6][0]:400 // 7,3,6
DP[6][1]:400 // 7,5,6
DP[7][0]:100 // 7
DP[8][0]:400 // 7,4,8
DP[8][1]:400 // 7,3,8
DP[8][2]:550 // 2,3,8
DP[9][0]:650 // 2,3,8,9
DP[9][1]:600 // 7,3,6,9
DP[9][2]:650 // 7,5,6,9
ans = 650
すべての要素のうち最大値が解答。実装
ll N;
ll H[3030]; // combo_score
ll M[3030]; // M[id] = eiga
ll E[3030]; // endtime
vector<pll> S[3030]; // 開始時間, id
ll DP[3010][3010]; // 映画id, combo
int main() {
cincout();
cin >> N;
rep(i, N) cin >> H[i];
vector<pll> timetable(N);
rep(i, N) {
ll m, s, e;
cin >> m >> s >> e;
--m;
M[i] = m;
E[i] = e;
S[m].push_back({s, i}); // 開始時間, id
// 開始時間が早いやつから探索したい
timetable[i] = {s, i};
}
rep(i, N) sort(all(S[i]));
sort(all(timetable));
ll ans = 0;
// 配るDPのようなもの。 配った時点で、相手先の遷移を確定。
rep(i, N) {
ll id = timetable[i].second;
ll eiga = M[id];
ll end = E[id];
// 初期入れ
chmax(DP[id][0], H[0]);
// 今時点のハイスコア出しとく。違う種類に行くときに使う。
ll high = 0;
rep(j, N) {
chmax(high, DP[id][j]);
if (DP[id][j] == 0) break;
}
// 全部の種類の、直近の映画を見に行く
rep(j, N) {
auto it = lower_bound(S[j].begin(), S[j].end(), make_pair(end, 0LL));
if (it == S[j].end()) continue;
// ちょっとよくない。間に合う映画の中で、終了時間が一番早い映画を全探
ll nid = it->second;
ll fastest = E[nid];
++it;
while (it != S[j].end()) {
if (fastest <= it->first) break;
ll &nowid = it->second;
if (chmin(fastest, E[nowid])) nid = nowid;
++it;
}
// もし同じ種類なら、コンボ加算。
if (eiga == j) {
rep(k, N) {
if (DP[id][k] == 0) break;
chmax(DP[nid][k + 1], DP[id][k] + H[k + 1]);
chmax(ans, DP[nid][k + 1]);
}
}
// 違う種類なら、0だけ。
else {
chmax(DP[nid][0], high + H[0]);
chmax(ans, DP[nid][0]);
}
}
}
cout << ans << endl;
// debug();
}https://atcoder.jp/contests/code-formula-2014-final/submissions/28614054