けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder EDPC Q - Flowers

まさに重み付き LIS ともいうべき問題ですね。

問題概要

 N 本の花が横一列に並んでいます。 左から  i 番目の花の高さは  h_{i} で、美しさは  a_{i} です。

太郎君は何本かの花を抜き去ることで、次の条件が成り立つようにしようとしています。

「残った花を左から順に見ると、高さが単調増加になっている」

残った花の美しさの総和の最大値を求めてください。

制約

  •  1 \le N \le 2 \times 10^{5}
  •  h_{1}, \dots, h_{N} 1, \dots, N の並び替え

解法

もし  a_{i} = 1 ならば、LIS (Longest Increasing Subsequence) そのものですね。この問題は  a という重みのついた、重み付き LIS とも呼ぶべき問題となっています。

よって、LIS によく似た解法で解くことができます。LIS を含めた詳しい解法は次の記事に記しました。

qiita.com