問題概要

$N$ 個のブロックからいくつかを選び、それらを積み重ねてタワーを作ります。

$i$ 個目のブロックは重さ $w_i$ 、頑丈さ $s_i$ 、価値 $v_i$ であり、 $i$ 個目のブロックよりも上に載っているブロックの重さの総和が $s_i$ を超えると耐えきれずこわれてしまいます。

タワーの価値を最大化してください。

解法

載せる順番まで全部試すと到底間に合わないので、ブロックを見る順番を適当にソートしてから貪欲っぽくDPをやらないと無理だろという気持ちになります。

直感に頼ると、頑丈なブロックを下の方に置きたくなります。置きたくなりますよね？ですが単純に $s_i$ の大きい順にソートすると、 $(w_1, s_1, v_1)=(1, 2, 1),$ $(w_2, s_2, v_2)=(100, 1, 1)$ みたいなときに破滅します。下から $2\rightarrow1$ の順に乗せれば価値は $2$ になりますが、 $s_i$ の大きい順でソートしてから $1\rightarrow2$ の順に見るとどちらか片方しか乗せることができません。

そこで、頑丈さの定義を変えてしまうことにします。具体的には、 $i$ 番目のブロックが自分自身の重量 $w_i$ も支えると考えて、 $s_i'=s_i+w_i$ と置いてあげます。こうすると、ある点より上のタワーの頑丈さを、ブロックを置いた後ではなく置く前に決められる（ $i$ 番目のブロックを使う／使わないに関わらず、それ以降の重量制限が $s_i'$ になると考えることができる）ので、 $s_i'$ の大きい順に見ていくことで上手く行くようになります。

順番さえ決めてしまえば、 $dp[i][j]$ ：ソート後の $i$ 番目のブロックまで見て、あと残り重さ $j$ まで乗せられるときの価値の最大値としてナップサックっぽいDPをすればよいです。計算量は $O(N(\log N+\max s_i'))$ です。

public override void Solve(IOManager io)
{
    var n = io.ReadInt();
    var blocks = new (int stiffness, int weight, int value)[n];

    for (int i = 0; i < blocks.Length; i++)
    {
        var w = io.ReadInt();
        var s = io.ReadInt();
        var v = io.ReadInt();
        blocks[i] = (s + w, w, v);  // s_i' = s_i + w_iとおく
    }

    blocks.Sort((a, b) => b.CompareTo(a));
    const int MaxStiffness = 20000;
    var dp = new long[n + 1, MaxStiffness + 1];

    for (int i = 0; i < blocks.Length; i++)
    {
        // s_i', w_i, v_i
        var (stiffness, weight, value) = blocks[i];
        // 本来のs_i
        var upperStiffness = stiffness - weight;

        for (int s = 0; s <= MaxStiffness; s++)
        {
            // i番目のブロックを採用しない
            dp[i + 1, s].ChangeMax(dp[i, s]);
            
            // i番目のブロックを採用する
            // i番目より上に載せられるのはs-w_iかs_iのどちらか小さい方
            var next = Math.Min(s - weight, upperStiffness);
            if (next >= 0)
            {
                dp[i + 1, next].ChangeMax(dp[i, s] + value);
            }
        }
    }

    long result = 0;

    for (int i = 0; i <= MaxStiffness; i++)
    {
        result.ChangeMax(dp[n, i]);
    }

    io.WriteLine(result);
}

不等式を立てて場合分けすることでソートの比較関数を導く解法が主流かと思いますが、こういう考え方もあるよということで書いてみました。

こちらの方が個人的には直感的かな？と思っていますが、いかがでしょうか？

TERRYのブログ

最近は競技プログラミングにお熱。

EDPC X - Tower 解説

問題概要

解法