思路
窗口滑动思路:
[i, i+ v,i + 2v, … , i + sv], … ,[j - sv, j - (s - 1)v, … , j - v, j]
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010;
int n, V;
int q[M];
int f[M], g[M];
int main()
{
cin >> n >> V;
for (int k = 0; k < n; k ++)// 总共更新n次, 即选取前k + 1的物件
{
int v, w, s;// 每选取一个物件
cin >> v >> w >> s;// 窗口大小为s
memcpy(g, f, sizeof g);// 不能直接修改上一层
for (int i = 0; i < v; i ++)// 余数部分
{
int hh = 0, tt = -1;
for (int j = i; j <= V; j += v)
{
// 对于每一项来说由滑动窗口在O(1)内给出最大值
if (hh <= tt && q[hh] < j - s * v) hh ++;
while (hh <= tt && g[q[tt]] + ((j - q[tt]) / v) * w <= g[j]) tt --;
q[++ tt] = j;
f[j] = g[q[hh]] + ((j - q[hh]) / v) * w;// 更新每一项的最小值
}
}
}
cout << f[V];
}