7K12 blog

猫でも分かるアルゴリズム解説

MinMax法

f:id:tkr987:20200301190858p:plain

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]の N^2のネストにする

左の数字を追加するか右の数字を追加するか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], にゃあ)のような書き方はしない。

 

天才的要素が多すぎないか?凡人が実装するためのアドバイスを求む…