問題
atcoder.jp
解法
区間DPで解く。
区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。
𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、最適な状況下での何かしらの値
dp[0][0]から、幅0でdp[0][0], dp[1][1], dp[2][2] ....と計算していく。
先攻後攻を考慮して
先攻ではX-Yが最大になるように
後攻ではX-Yが最小になるように
数字を入れていく。
最終的にdp[0][N-1]が計算され、答えが出る。
実装
参考
atcoder.jp
algo-logic.info
