概要

山頂を左から順に見ていき、標高が狭義増加するように高々 \(K\) 個選び、合計入山料が \(B\) 以下になる範囲で「選べる山頂数の最大値」を求めます。

考察

この問題は「番号の昇順に進む」「選んだ山頂の標高が増加」という条件から、増加部分列（LIS）に似た形をしています。ただし今回は「長さ最大」だけでなく、各山頂にコスト \(C_i\) があり、合計が予算 \(B\) 以下という制約もあります。

• 素朴に「選ぶ/選ばない」を全探索すると \(2^N\) となり、\(N \le 500\) では到底間に合いません。
• 「標高でソートして…」のような工夫をしても、山頂番号の順に進む制約（\(i_1 < i_2 < \cdots\)）があるため、結局は「前にある山頂からつなぐ」形のDPが自然です。
• ここで重要な観察は、“長さ \(l\) の増加列を作るための最小コスト”を持てば、予算 \(B\) 以内かどうかを判定できる、という点です。
  つまり「最大長」問題を、「各長さに対して最小コストを求める」問題に変換します。

アルゴリズム

DPを次のように定義します。

• \(dp[i][l] =\) 「山頂 \(i\) を最後に選ぶ、長さ \(l\) の標高増加列」を作るために必要な入山料合計の最小値
  （作れない場合は \(\infty\) 扱い）

遷移はLISと同様に「1つ前の山頂 \(j\) からつなぐ」形です。

1. 初期化

   • 山頂 \(i\) を単独で選ぶ：
     \(dp[i][1] = C_i\)

2. 遷移

   • \(j < i\) かつ \(S_j < S_i\) のとき、山頂 \(j\) の列の後ろに \(i\) を付けられるので
     \(dp[i][l] = \min\left(dp[i][l],\ dp[j][l-1] + C_i\right)\)
     
   • ただし、予算判定を簡単にするため、\(B\) を超えたら \(\infty\)（コードでは \(B+1\)）として扱います。

3. 答えの更新

   • どこかの \(i\) について \(dp[i][l] \le B\) が成り立てば、長さ \(l\) は実現可能です。
     その最大の \(l\)（ただし \(l \le K\)）を答えにします。

具体例（イメージ）

例えば「長さ2で終点が \(i\)」を作りたいときは、 - \(i\) より左にある山頂 \(j\) の中で - 標高が \(S_j < S_i\) を満たし - かつ \(dp[j][1] + C_i\) が最小になるもの を探せばよい、ということになります。これを長さ \(3,4,\dots\) に拡張したのが今回のDPです。

計算量

• 時間計算量: \(O(N^2 K)\)
  （各 \(i\) について全ての \(j<i\) を見て、長さ \(2..K\) を更新）
• 空間計算量: \(O(NK)\)
  （\(dp\) 配列）

制約内では \(500^2 \times 50 = 12{,}500{,}000\) 程度なので十分間に合います。

実装のポイント

• \(\infty\) は「予算 \(B\) を超えた」状態として扱えればよいので、コードでは INF = B + 1 としています（これで <= B 判定が簡単）。

• 登頂数の上限は \(K\) ですが、当然 \(N\) を超えられないため L = min(K, N) としています。

• dp[j][l-1] がすでに > B の場合、それ以上足しても無駄なのでスキップし、定数倍を軽くしています。

• 答えは「どの終点でもよい」ので、各 \(i\) ごとに dp[i][l] <= B を見て最大の \(l\) を更新します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K, B = map(int, input().split())
    C = [0] * N
    S = [0] * N
    for i in range(N):
        c, s = map(int, input().split())
        C[i] = c
        S[i] = s

    L = min(K, N)
    INF = B + 1

    dp = [[INF] * (L + 1) for _ in range(N)]
    ans = 0

    for i in range(N):
        ci = C[i]
        dpi = dp[i]
        dpi[1] = ci
        if ci <= B:
            ans = max(ans, 1)

        si = S[i]
        for j in range(i):
            if S[j] < si:
                dpj = dp[j]
                # length 2..L
                for l in range(2, L + 1):
                    prev = dpj[l - 1]
                    if prev <= B:
                        val = prev + ci
                        if val > B:
                            val = INF
                        if val < dpi[l]:
                            dpi[l] = val

        for l in range(2, L + 1):
            if dpi[l] <= B and l > ans:
                ans = l

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。