主食は米

主に競プロ備忘録

SoundHound Programming Contest 2018 Masters Tournament Open B - Neutralize(400)

解法

  • K個以上の区間は消せる
  • Greedyは厳しそう
  • dp[i] := (最後に[i,i+K) を消したときのmax ) とすると..?
  • dp[i+1] = max_{ j, [i,i+K) と [j,j+K) の区間が被っている } ( dp[j] + sum_b [j+K, i+K) ) と,
  • dp[i+1] = max_{ j, [j,j+K) の区間は [i,i+K) と被らない } ( dp[j] + sum_b[i,i+K) ) の漸化式が立つ
  • 愚直O(N2), 累積和+区間和とRMQのSeg木でO(NlogN)だが400点なのでさすがに...

  • 上の置き方は最後に消した場所を持っていて,まとめ方が良くなさそう

  • どの範囲が0か,ではなく末尾が0かだけを持っておこう
  • dp[i][j] := ( b[0,i) についての max, j は末尾が0かどうか ) とおく
  • dp[i+1][1] = max(dp[i-K+1][0] , dp[i][1] )
  • [i-K+1, i+1) を消す時,その範囲の j==0 の場合の更新はないものになる and 1個前が0の時はその数は好きに0にできるため
  • dp[i+1][0] = max(dp[i][0], dp[i][1]) + b[i] という漸化式が立つ

メモ

飛び地で更新する?系のDPに弱い

コード