JOI2018/2019 予選ページ：E - イルミネーション (Illumination)
問題
https://www.ioi-jp.org/joi/2018/2019-yo/2019-yo-t5-review.html
数列 と
個の区間
が与えられる。数列
からいくつかの要素
を選び、その総和を求める。ただし
個の区間に含まれる要素は
つしか選ぶことができない。
この時、総和の最大値を求めよ。
制約
考え方
区間に含まれる要素は つしか選ぶことができない点が重要である。つまり区間に含まれる
を選んだとき、
を被覆する区間のうち、
の最大値を
とすると次に選ぶことができるのは
である。
区間の最大値は数列の左から決めていくことができるのでDPで求めることができる。予め を選んだときに制約区間に被覆される最大の
を求めておく。
番目までの総和の最大値
とする。DP遷移は、 を選ぶ場合と選ばない場合のそれぞれで定まり、
を選ばない場合は
である。 を選ぶ場合は
である。解は となる。
Submission #3836041 - JOI2018/2019 予選ページ
どこに着目して考察するべきだったか
制約によって、 を選ぶ場合は次に選ぶことができるのは
の要素であることがわかると、配るDPに気づけるかもしれない。