SoundHound Programming Contest 2018 本戦 B「Neutralize」解法
みなさん、どうも、@ukohank517です。
SoundHound 2018本戦B問題について、 解説と違う解法で解いたので、ここでメモを残しておこうと思います。
考え方
連続K個以上非正の効用が続いてたらそれらを全部0にして構いません。
K個以上連続してなければちょっとややこしいですね。
要するに、dp問題です。
解法
dp[i][j] (0 <= i <= N, j = {0,1} )の配列を用意する
- インデックス:
- iは更新する配列の番号、配列の末端から先端より逆順で考慮する。
- jの0,1はfalse/trueと理解して問題ないです。
- 意味: i+1 番目以降を全て最適にする時、i番目の薬品の処理(0にするかどうか)によって得られた最大効用
- インデックス:
初期化: 薬品が存在しない時、0にしなくても【dp[N][0]】効果が0
- 後ろから更新:
- i番目の効果を0にしたければ【dp[i][1]】：①「自分を含む、自分からK-1番目先全部0にする時、K番先の薬効用を利用する値【dp[i+K][0]】になる」②「連続K品以上の薬効用を無視していれば、自分の一品もついでい0にする【dp[i+1][1]】」の二つの値より大きい方を利用する
- i番目の効果を0にしなければ【dp[i][0]】、i+1までの最適解 【max(dp[i+1][0], dp[i+1][1])】にi番目【b[i]】の効果を足す
参考コード
一言
この問題が400点問題？！
企業コン恐ろしい。。
