はまやんはまやんはまやん

hamayanhamayan's blog

異世界転生2 [Kodamanと愉快な仲間たち J]

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