标签:动态规划-单调队列优化DP

题意多重背包问题。题解单调队列优化多重背包。$$f[i][j] = \max_{k=0}^{num[i]} f[i-1][j-k\times c[i]]+k\times w[i]$$令 $a = j \mod c[i] \ , \ b = \lfloor \dfrac{j}{c[i]} \rfloor $ :$$f[i][j] = \max_{k=b-num[i]}^{b} \{f[i-1]...
题解 动态规划 动态规划-单调队列优化DP
提高+/省选-
题意从一个数列中选出一些数,要求不能有超过 $k$ 个连续的数,求这些数的最大和。数列长度 $N\le 100000$ 。题解令 $f[i]$ 表示前 $i$ 个数的最优解,$sum[i]$ 表示前缀和,转移方程式为:$$f[i] = \max_{j=i-k}^i f[j-1] + sum[i] - sum[j]$$$$f[i] = \max_{j=i-k}^i \{f[j-1] - sum...
题解 动态规划 动态规划-线性DP 动态规划-单调队列优化DP
提高+/省选-