JOI難易度６ 古本屋

問題原文

https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=4

問題要旨

冊の本のうち、 冊を売ることを考える。 番目の本の買取価格は である。
また、本には10種類のジャンルがあって、同じジャンルの本をまとめて 冊売ると、１冊あたり 円買取価格が上がる。
最適に売る本を選んだ時の、最大合計買取価格を求めよ。

• 
• 
• 本のジャンルは最大10種類

解法

まず、あるジャンルについて売る冊数を決めたなら、買取価格が高い方から売っていくのがよい。
また、買取価格が高い方から 冊売った時の 合計買取価格は累積和を取っておくと都度高速にわかる。

ここまで浮かべば自然に dpが浮かんで、
「 種類目まで見て、 冊売っている時の、最大合計買取価格 」 という素直なdpテーブルで解ける。

遷移は「 種類目まで見て、」「ジャンル について 冊売って」「これまでの合計 冊売ったことになるとき」の、最大合計買取価格、のような形で回るため、実際のループは３重になる。
ぱっと見間に合わなさそうだが、 冊売って〜の部分が結局合計で 回しか回らないので結局 になる。（あってる。。。？）

実装

from itertools import accumulate
N, K = map(int, input().split())
Books = [[] for _ in range(10)]
for _ in range(N):
    c, g = map(int, input().split())
    g -= 1
    Books[g].append(c)

for g in range(10):
    Books[g].sort(reverse=True)
    Books[g] = [0] + list(accumulate(Books[g]))

# dp[g][k] := g種類目まで見て、k冊売っているときの最大値
dp = [[0] * (K + 1) for _ in range(11)]
for g in range(10):
    # u冊売る
    for u in range(len(Books[g])):
        for k in range(K + 1):
            if k + u > K:
                break
            dp[g + 1][k + u] = max(dp[g + 1][k + u], dp[g][k] + Books[g][u] + max(0, u - 1) * u)

print(dp[-1][-1])

感想

このdpを自然だと思えるようになったのは成長かなぁ。。。