https://atcoder.jp/contests/dp/submissions/10388277
MinMax法を実装するために以下を暗記すると効率が良いと思う。
- 片方min片方maxでdp漸化式を書く
- 最大化するときは+a[i]、最小化するときは-a[i]で符号を変えるだけで対応できる
ただし、これだけの知識では今回の問題は実装できない。以下に気づく必要がある。
- 逆順で処理しても最適解が得られる
- dp[i][j]の[j]を開区間にすると実装が簡単
- 数列の長さ0から始めてNまで決め打ちしながらdpを更新してく
- [j]はN-iとすることでループはNと[i]の
のネストにする
左の数字を追加するか右の数字を追加するか2通りあるので漸化式の形は
dp[i][j] = max(dp[i][j - 1] + a[j - 1], dp[i + 1][j] + a[i]);
dp[i][j] = min(dp[i][j - 1] - a[j - 1], dp[i + 1][j] - a[i]);
数列の長さを決め打ちして数列左端の位置を表す[i]を全探索することで網羅する。
[j]はN-iなのでループを省略できる。
なお、今回は必ずdpが更新されるのでdp[i][j] = max(dp[i][j], にゃあ)のような書き方はしない。
天才的要素が多すぎないか？凡人が実装するためのアドバイスを求む…
