Activities [第六回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202104-open/tasks/past202104_n

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/past202104-open/submissions/22661300

最小費用流とか貪欲法とか微妙に色々見える問題とか制約になってはいるが、考えてみるとオーソドックスにDPで解ける。
解けるのだが、工夫が必要である。

何から考えるか

普通のDPと違う部分として、得られる利得が体力を使っている部分である。
なので、

dp[i][h] := i番目まで活動を終えていて、体力がhであるときの得点の最大値

という風なDPを作って、体力が状態に入っているので利得が計算できてよさそうである。
実はDPテーブルはこれでいいのだが、注意点がある。

DPは順番が関係する場合は使えない

活動1→活動2とやる場合と活動2→活動1とやる場合では最終的な得点が異なる場合がある。
普通のナップサックDPではこのような順番を入れ替えるようなことはできず、固定化した順番でしか状況を全探索できない。
これを打開するために、「あらかじめ最適なソートを行ってからDPすることで最適解を得る」ことにする。
類題としては、
競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん
ここの「特殊なソートで最適解を得るテク」にある。
動的計画法のテクの1つであるともいえる。

どのような順番が適切か

これは単純に隣接している2要素について得点が増加するかを考えればいい。
活動iと活動jをi→j、j→iのどちらでやるのが得点が高いかを使ってソート用の比較関数を用意する。

a[i]*H + a[j]*(H - b[i]) > a[j]*H + a[i]*(H - b[j])  
a[i]*H + a[j]*H - a[j]b[i] > a[j]H + a[i]*H - a[i]b[j]  
a[i]b[j] > a[j]b[i]  
a[i] / b[i] > a[j] / b[j]  

このように得点が最大化するように降順っぽい条件を書き下してきれいにする。
すると、a[i]/b[i]の降順で並べれば最適な順番となるので、それでソートをしたのち、単純な最大値DPを行っていく。
比較関数で比較するときは分数による誤差が気になるので、下から二番目の積での比較をやるといい。

あとは、活動後に体力が0未満になる場合も考えて答えの最大値を更新していって、答える。

int N, H;
vector<pair<int, int>> AB;
ll dp[101][101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> H;
    rep(i, 0, N) {
        int a, b; cin >> a >> b;
        AB.push_back({ a, b });
    }
    sort(all(AB), [&](auto a, auto b) { return 1LL * a.first * b.second > 1LL * a.second * b.first; });

    rep(i, 0, N + 1) rep(h, 0, H + 1) dp[i][h] = -infl;
    dp[0][H] = 0;

    ll ans = -infl;
    rep(i, 0, N) rep(h, 0, H + 1) if (-infl < dp[i][h]) {
        chmax(dp[i + 1][h], dp[i][h]);
        if (0 <= h - AB[i].second) chmax(dp[i + 1][h - AB[i].second], dp[i][h] + 1LL * AB[i].first * h);
        chmax(ans, dp[i][h] + 1LL * AB[i].first * h);
    }
    cout << ans << endl;
}