精進 ARC074D - 3N Numbers
おおー500点とかびびってたけど
最近の精進が効いてきてるみたいで自力で解けた嬉しい
さて方針
吸収していく、というイメージを持ちました
入力例1 2 3 1 4 1 5 9
これを右側と左側で分けてみると
[ 3 1 ] 4 1 [ 5 9 ]
左側は大きく、右側は小さくしていくのが目標ですね
左から3番目の4を考えてみよう
左側を大きくすることだけを考えれば
左側のグループで最小の1を捨てて、4を吸収するのがいいですね
また、
右から３番めの1を考える
右側を大きくすることを考えれば
右側のグループで最大の9を捨てて、1を吸収するのがいいです
これを方針とします
ここからがちょっと問題
ただし、どこまでを左側のグループで考えるか、
どこまでを右側のグループで考えるかを
決めることは不可能です
これは、全部試さなきゃダメ(この方針が今の僕に大切だと思う)
よく考えると
それぞれのグループの和はDPで求めることができます
これを利用して計算すればすべて試すことができる
O(NlogN)で通りました
