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に弱い
