单调队列求滑动窗口最大值

并不是简单的求滑动窗口最大值, 需要先进行变形:
dp[j + k * v] - k * w
求得的滑动窗口最大值
最后还需要加k * w加回来.
自己推导一下公式, 就能理解为什么要这么做了.

时间复杂度

O(N * V)

Python 代码

from collections import deque

N, V = map(int, input().split())
dp = [0] * (1 + V)

for i in range(N):
    v, w, s = map(int, input().split())
    for j in range(v):
        Q = deque()
        for k in range((V - j) // v + 1):
            val = dp[j + k * v] - k * w
            while Q and Q[-1][0] <= val:
                Q.pop()
            while Q and k - Q[0][1] > s:
                Q.popleft()
            Q.append((val, k))
            dp[j + k * v] = Q[0][0] + k * w
print(dp[-1])