Tower [Educational DP Contest / DP まとめコンテスト X]

https://atcoder.jp/contests/dp/tasks/dp_x

前提知識

• 動的計画法テク「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」

解説

https://atcoder.jp/contests/dp/submissions/3980762

動的計画法で困るのが、順番が任意である場合である。
しかし、場合によっては最適な順番があり、固定できる場合がある。
仮に最適な順番があるとした場合は、
dp[i][tot] := i番目までを使って、重さの総和がtotである場合の価値の総和の最大値
とDPを立てることができ、更新も使う使わないの2通りなので、解ける。
なので、最適な順番にソートできないか考えてみる。
　
C++なら大体sort関数を作るが、これはある2項について考えるものであり、ソートしてからDPする場合は大体2項について考えればいい。
ブロックaとブロックbのどちらが上の方がいいかの判定を考える。
既に総重量xのブロックが積まれているとすると、
　

• 総重量xのブロック、ブロックa、ブロックbであるとき

x ≦ S[a]
x + W[a] ≦ S[b]
を満たす必要があるので、x ≦ min(S[a], S[b]-W[a])

• 総重量xのブロック、ブロックb、ブロックaであるとき

x ≦ S[b]
x + W[b] ≦ S[a]
を満たす必要があるので、x ≦ min(S[b], S[a]-W[b])
　
使えるxが多いほうが最適であるので、2つの要素については
a＜bであれば、min(S[a], S[b]-W[a]) ＞ min(S[b], S[a]-W[b])をみたせばいい。
これでソートして、DPする。

int N, W[1010], S[1010], V[1010];
ll dp[1010][30101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> W[i] >> S[i] >> V[i];
 
    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    sort(all(ord), [&](int a, int b) { return min(S[a], S[b] - W[a]) > min(S[b], S[a] - W[b]); });
 
 
    rep(i, 0, N) rep(tot, 0, 20101) {
        int a = ord[i];
        chmax(dp[i + 1][tot], dp[i][tot]);
        if(tot <= S[a]) chmax(dp[i + 1][tot + W[a]], dp[i][tot] + V[a]);
    }
 
    ll ans = 0;
    rep(tot, 0, 20101) chmax(ans, dp[N][tot]);
    cout << ans << endl;
}