概要 N本の花が一列に並んでいて、各花には高さhと美しさaがあります。花の高さはすべて異なります。ここから花を抜き去って残った花の高さが単調増加になるようにしたとき、残った花の美しさの総和の最大値を求めてください。 考え方 1.SegmentTree解法 ・美しさaがすべて1である場合 →高さが単調増加するようになるべく多く花を取る問題になる。これはLISにほかならない これは、次のようなDPを保持した動的計画法で求められる DP[i]=残った花の高さのMAXがiであるときの、残った花の数 遷移:i=1...nについて、以下を行う。DP[0],DP[1]...DP[h[i]-1]の区間maxを…