2022-05-07 EDPC DP Contest の Q を解いた
EDPC : Educational DP Contest の Q を解いた。
- Q - Flowers
https://atcoder.jp/contests/dp/tasks/dp_q
- 提出: https://atcoder.jp/contests/dp/submissions/31479194
- 解説 AC: https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
- 先頭から走査して最後の花の高さごとの美しさの総和の最大値を保持する
- 各要素ではその花の高さの場所を「その花の高さ未満の美しさの総和の最大値 + その花の美しさ」で更新すれば良い
- 「その花の高さ未満の美しさの総和の最大値」はセグメント木で高速に得られる
- 解説を見てしまうと、なぜ分からなかったのかが分からない
『ソフトウェアアーキテクチャの基礎』を読み終えた。
今日のコミット。