DPまとめコンテスト X - Tower
問題
$ N個のブロックがあり、ブロック$ iの重さが$ w_i、丈夫さが$ s_i、価値が$ v_iです。
このブロックの一部を使い以下の条件を満たすように塔を作ります。
塔に含まれる各ブロック$ iについて、ブロック$ iより上に積まれたブロックの重さの総和は$ s_i以下である。
塔に含まれるブロックの価値の総和の最大値を求めてください。
制約
入力はすべて整数
$ 1 \leq N \leq 10^3
$ 1 \leq w_i,s_i \leq 10^4
$ 1 \leq v_i \leq 10^9
考察
0-1 ナップサック問題に似ていますが、丈夫さという要素が入っています。丈夫さのおかげで、ブロックに何らかの順序が必要そうです。 問題を直接考えるのが難しいので、もとの問題より簡単そうな問題として、
ブロックが与えられたときに、すべてのブロックを使うことができるか?
という問題を考えてみます。
まず、一番考えやすい部分は1番下に置けるブロックが存在するか?だと思います。
これは問題文から$ s_i \geq \sum_{j \neq i}^N w_j を満たす$ iが存在するかどうかでわかります。
この式は$ \sum_{j=1}^N w_j = Wとおくと
$ s_i \geq W - w_i \Leftrightarrow s_i + w_i \geq Wと書き換えられます。
この書き換えの嬉しいところは、$ iに関わる部分が左辺のみにまとまっているところです。
したがって、ブロックを$ s_i + w_iでソートして、$ W以上となるものがあるかどうかを調べることで1番下に置けるブロックが存在するかがわかります。
$ s_i + w_i \geq Wとなる$ iが2つ以上あった場合にはそれらはどの順序で置いても良いです。なぜならブロック$ jを使ってその上に置けるのは$ s_i + w_i \geq W - w_jを満たす$ iで、$ Wよりも条件がゆるくなっているので当然$ s_i + w_i \geq Wを満たしていたものは置けるからです。なので、$ s_i + w_iで降順ソートしたら、その後は順番に置いていけばよいです。
つまりブロックが与えられたときに、すべてのブロックを使うことができるか?は以下のように$ O(N \log N)で解けます。
ブロックを$ s_i + w_iを降順でソートしたあとは、
$ s_1 + w_1 < Wならすべて使うことはできない。
$ s_1 + w_1 \geq Wならブロック1を置く。
ブロック2以降のみで$ W \rightarrow W - w_1とした同じ問題を解く。$ Nまで置けたらすべて使えるということ。
さて、ブロックが与えられたときに、すべてのブロックを使うことができるか?という問題は、$ s_i + w_iで降順ソートした後は
1番目以降のブロックを使い総重量$ W以下で塔で作ることができるか?
という問題になっていることがわかり、その過程には
2番目以降のブロックを使い総重量$ W - w_1以下で塔を作ることができるか?
3番目以降のブロックを使い総重量$ W - w_1 - w_2以下で塔を作ることができるか?
$ \dots
と部分問題が現れることがわかります。この構造を利用してもとの問題をDPで解いてみましょう。 以下は0インデックスで考えます。まずブロックを$ s_i + w_iの降順でソートします。
$ {\rm dp}_{i,j}を$ \lbrack 0, i)までを利用し、残りのブロックの総重量が$ j以下となるような塔の価値の最大値とします。$ {\rm dp}_{0,j} = 0で、考える必要がある$ jは$ j \leq \max_k \{ s_k + w_k\} \equiv Sです。
$ i番目を使わない場合
$ {\rm dp}_{i+1,j} = \max({\rm dp}_{i+1,j}, {\rm dp}_{i,j})
$ i番目を使える場合$ \Leftrightarrow j - w_i \geq 0, s_i + w_i \geq j
$ {\rm dp}_{i+1,j-w_i} = \max({\rm dp}_{i,j-w_i}, {\rm dp}_{i,j} + v_i)
$ i番目を使わない場合
$ {\rm dp}_{i+1,j} = \max({\rm dp}_{i+1,j}, {\rm dp}_{i,j})
$ i番目を使える場合$ \Leftrightarrow j + w_i \leq S, s_i + w_i \geq j + w_i
$ {\rm dp}_{i+1,j} = \max({\rm dp}_{i+1,j}, {\rm dp}_{i,j + w_i} + v_i)
となります。$ iに関する部分は再利用できます。
時間計算量は$ O(Nlog N + NS)です。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N;
struct Block {
int w, s, v;
};
vector<Block> B;
int main() {
cin >> N;
B.resize(N);
int S = 0;
rep(i, N) {
cin >> Bi.w >> Bi.s >> Bi.v; }
sort(B.rbegin(), B.rend(),
&(const Block& a, const Block& b) { return a.s + a.w < b.s + b.w; }); vector<ll> dp(S + 1, 0);
rep(i, N) rep(j, S + 1) {
if (j + Bi.w <= S && Bi.s >= j) dpj = max(dpj, dp[j + Bi.w] + Bi.v); }
return 0;
}