https://atcoder.jp/contests/dp/tasks/dp_x
解説
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; }