(飽きたので途中までしか書いていません) 解説 ABC162 F - Select Half

F は DP の F！

問題

提出

基本方針

こんなんどっからどうみても DP やんけ！dp[i][j] := i (0 ≤ i ≤ N) 番目までで j (0 ≤ j ≤ N / 2) 個選んだときの和の最大値！おらどけどけどけどけ DPDPDPDP Θ(N²)Θ(N²)Θ(N²)Θ(N²) TLETLETLETLE → 高速化しよう

よくよく考えたら、i / 2 より j が大きすぎたり小さすぎたりするのは明らかにおかしいです。常に 0 ≤ (i + 1) / 2 - j ≤ 2 となっていなくてはいけません (たぶん)。なので、j 個選んだときではなく、j 個 (選べるのに) 選ばなかったときとすれば、0 ≤ j ≤ 2 となり、全体で Θ(N) になります。

(飽きたので終わり)