まさに重み付き LIS ともいうべき問題ですね。
問題概要
本の花が横一列に並んでいます。
左から
番目の花の高さは
で、美しさは
です。
太郎君は何本かの花を抜き去ることで、次の条件が成り立つようにしようとしています。
「残った花を左から順に見ると、高さが単調増加になっている」
残った花の美しさの総和の最大値を求めてください。
制約
は
の並び替え
解法
もし ならば、LIS (Longest Increasing Subsequence) そのものですね。この問題は
という重みのついた、重み付き LIS とも呼ぶべき問題となっています。
よって、LIS によく似た解法で解くことができます。LIS を含めた詳しい解法は次の記事に記しました。
