DP W
0と1からなる長さ20万の列があって「この範囲に1があれば何点」というルールが20万個ある、最良の列を作ったら何点になるか求めよ
素朴に実装したらどうなるか
2^200000の各数列に対してスコア計算してmax→やばい
各数列について計算する代わりに、途中までの結果を使って効率よく計算できないか？
> dp[i] = （i まで決めたときに）最後に1にしたのが i であるときのmax。遷移は dp[i] = min(dp[j] | j=0~i-1) 。その後、区間 [l,i] について dp[l~i] に a を足しこむということをやる。segtreeで高速化する（区間addと区間minができれば良い）O((N+M) log N) > なんかこれは自分は典型化できてなかった（ので説明がふわっとしてしまっている）
Related Pages
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]