問題概要

N個のブロックがあり，i番目のブロックは重さ$ w_i $，価値$ v_i $であり，そのブロックには重さが計$ s_i $までのブロックを載せることができる．

これらのブロックを1列に積み上げてタワーを作るとき，タワーの価値の最大値を求めよ．

解法概要

Wは$ w_i, s_i$の取りうる最大値として， Wがそんなに大きくないので， $ dp_i = $全体の重さがiのときの全体の価値ができそう．あとは追加順序を固定できれば楽勝なのだが……．

追加順序のために，ブロック$ i$とブロック$ j$について考える．

もしや$ s_i \leq s_j $のとき，ブロックiはブロックjよりも上に置かれると考えて良いのでは？
- →入力例2が反例
かといって $ w_i \leq w_j $のときも順序の固定はできない
- めっちゃ軽くてめっちゃ力持ちなブロックは下に置かれるべき
それなら$ s_i+w_i \leq s_j+w_j $の場合はどう？
- 例えばブロックiを1番下に置いた場合，その地点での全体での重さは$ s_i+w_i$以下になるはずなので，それっぽい？
  - 証明できんの？→ということで，証明してみよう！

証明したいこと: 複数のブロックでタワーを作るとき，$ s_i+w_i \leq s_j+w_j$ であるブロックi,j について，ブロック j をブロック i の上に置けるならば，ブロック i をブロック j の上に置くことも必ずできる．

分かりづらいが，以下のメモのようなことが言いたい (図中の i と j の違いが分かりづらくてごめんなさい) ．

f:id:noimin:20190304190301j:plain

ブロック j をブロック i の上に置けるということは

$ w_0 + w_j \leq s_i$ ($ w_0$はブロック i と j よりも上に積み上げてあるブロックの重さの和) ．

したがって $ w_o \leq s_i - w_j$ (1)

また，$ s_i+w_i \leq s_j+w_j$ と仮定しているので$ s_i+w_i-w_j \leq s_j$ (2)

(1), (2) より

$ w_0 + w_i \leq s_i + w_i - w_j \leq s_j$

よって $ w_0 + w_i \leq s_j$で，ブロック i の上にブロック j を置くことができる．

以上より，ブロック j をブロック i の上に置けるとき，ブロック i をブロック j の上に置くことも必ずできる．

結論として，$ s_i+w_i$で並べ替えてナップサック問題を解くときと同様のDPをすれば良い．

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int MAX_W = 20000;

struct Block {
    ll w, s, v;    
    Block(ll w=0LL, ll s=0LL, ll v=0LL): w(w), s(s), v(v) {}
    bool operator<(const Block b) const{
        return w+s < b.w+b.s;
    }
};

ll dp[2][MAX_W+1];

int main() {
    int n;
    cin >> n;
    vector<Block> blocks(n);
    for(int i=0;i<n;++i) {
        cin >> blocks[i].w >> blocks[i].s >> blocks[i].v;
    }
    sort(blocks.begin(), blocks.end());

    // 上から置いていく
    dp[0][0] = 0LL;
    for(int i=0;i<n;++i) {
        int i_mlb = i & 1;
        for(int j=0;j<=MAX_W;++j) {
            dp[1-i_mlb][j] = max(dp[1-i_mlb][j], dp[i_mlb][j]);
            if(j+blocks[i].w <= MAX_W && j <= blocks[i].s) {
                dp[1-i_mlb][j+blocks[i].w] = max(dp[1-i_mlb][j+blocks[i].w], dp[i_mlb][j] + blocks[i].v);
            }
        }
    }

    ll ans = *max_element(dp[n&1], dp[n&1]+MAX_W+1);
    cout << ans << "\n";
}

所感

少し真面目 (※当社比) に考察 & 実装したのでメモを残しておく．

なぜその値でソートするのかや，なぜ貪欲で良いのかの証明パワーを強化したい．

NoiminのNoise

Educational DP Contest X - Tower

問題概要

解法概要

ソースコード

所感