Bounty Hunter

次のような動的計画法を考えます．
時刻 $i$ における体力 $j$ のときの得られる賞金の合計の最大を$dp[i][j]$ としたとき，遷移は

• モンスターを討伐する: $dp[i+1][j-1] = \max(dp[i][j-1], dp[i][j]+A_i) \quad (j \ne 0)$
• 休憩する: $dp[i+1][M] = \max(dp[i+1][M], dp[i][j])$
• 何もしない: $dp[i+1][j] = \max(dp[i+1][j], dp[i][j])$

となり，答えは $\max \limits_{0 \le j \le M} dp[N+1][j]$ となります． しかしこの動的計画法の時間計算量は $O(NM)$ と間に合いません．

また「何もしない」を選ぶとき「休憩する」を選べば良いため，「何もしない」は選ばなくても良いことが分かります．

これをいわゆる貰いdpに変換すると

• モンスターを討伐する: $dp[i][j] = dp[i-1][j+1] + A_i \quad (j \ne M)$
• 休憩する: $dp[i][M] = \max \limits_{0 \le j \le M} dp[i-1][j]$

になります．

ここで時刻 $i$ に「休憩する」をしたときの得られなかった賞金の合計の最小を $dp'[i]$ としたとき， $dp[i][j] = \sum_{k=1}^{i} A_k - dp'[i-j]$ より， $dp'[i]$ の遷移は

• 休憩する: $dp'[i] = \begin{cases} 0 &\text{if} \: i \le 0 \\ \min \limits_{0 \le j \le M} dp'[i-j-1] + A_i &\text{if} \: 1 \le i \le N \end{cases}$

となり，答えは $\sum_{i=1}^{N} A_i - \min \limits_{0 \le i \le M} dp'[N-i]$ となります．

$B_i = \{i-j-1 \: | \: 0 \le j \le M\}$ としたとき $B_i = (B_{i-1} \setminus \{i-M-2\}) \cup \{i-1\}$ であるため，multiset等を用いることにより $\min \limits_{b \in B_i} dp'[b]$ を $O(\log M)$ で求めることができます． よって時間計算量 $O((N+M)\log M)$ となり間に合います．

また，遅延セグメント木を用いてインラインDPをすることでも解くことが可能です．

想定ソースコード