問題
提出コード
すんなり考察&実装がいったので結構好きです。
解法
1つも入手しない宝石の種類を1つ決めると、それ以外の全ての宝石は獲得しても問題ありません。これについて考えるとき、2種類目以降の獲得しない宝石が存在しようがしまいが関係ありません。
ということで、
memo[i] = i番目の宝石を獲得しない、と決めたときに得られる得点の最大値
という配列を埋めていくことを考えます。
番目の遺跡を探索すると、
から
までの宝石を入手します。得点は
です。
ということは、先ほどの配列について考えると、iが
～
までと、
～
場所に、を追加できますこれは、
番目の遺跡を探索しても、上記の区間内の宝石は獲得しないので、配列の条件を満たすからです。
これをすべてのについて行えばいいのですが、配列の要素1つ1つに
を追加していると間に合いません。
区間のすべてに要素を追加するので、いもす法を使います。
memo[1]とmemo[ ]に
を追加し、memo[
]とmemo[
]から
を引きます。これをすべての
について行い、最後にmemo[1]から順番に累積和をとっていくと、配列の計算が完了します。
あとは、これらすべての要素を確認して、その中の最大値をとってくれば答えとなります。
