https://www.hackerrank.com/contests/kodamanwithothers/challenges/2-82
解説
https://www.hackerrank.com/contests/kodamanwithothers/challenges/2-82/submissions/code/1316477943
パっと見てDPな感じ。 区間で、最大値で、かぶってはいけない。 今まで何度も見てきたDPではあるが、A,Bのがとても大きい値になっている。 A,Bの機関は特に問題ではなく、かぶっているかどうかだけ分かればいいので、座標圧縮してしまって問題ない。 座標圧縮してしまえば、以下のDPで更新できる。 dp[t] := 時刻tから仕事ができるときの神様の嬉しさの合計の最大値 仕事の時刻Aでまとめたクエリを用意しておき、dp[t]を更新するときにdp[t+1]に加えて、 仕事をしたときの遷移も行う。
int N, A[101010], B[101010], C[101010]; ll dp[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i] >> B[i] >> C[i]; vector<int> dic; rep(i, 0, N) dic.push_back(A[i]); rep(i, 0, N) dic.push_back(B[i]); sort(all(dic)); dic.erase(unique(all(dic)), dic.end()); rep(i, 0, N) { A[i] = lower_bound(all(dic), A[i]) - dic.begin(); B[i] = lower_bound(all(dic), B[i]) - dic.begin(); } int M = dic.size(); vector<vector<int>> que(M); rep(i, 0, N) que[A[i]].push_back(i); rep(t, 0, M) dp[t] = -infl; dp[0] = 0; rep(t, 0, M) { chmax(dp[t + 1], dp[t]); fore(i, que[t]) chmax(dp[B[i]], dp[t] + C[i]); } cout << dp[M] << endl; }