单调队列优化DP
算法步骤:
- 第一个元素进队,队头队尾指针指向第一个元素
- 对于其他的N-1个未入队的元素,执行以下操作
for(int i = 1 ; i <= n ; i ++){ cin >> c[i] >> w[i] >> num[i];//c, w, num分别对应 体积 价值 个数 if(V / c[i] < num[i]) num[i] = V / c[i];//求lim for(int mo = 0; mo < c[i]; mo ++){//枚举余数 head = tail = 0;//队列初始化 for(int k = 0; k <= (V - mo) / c[i]; k++){ int x = k; int y = dp[k * c[i] + mo] - k * w[i]; while(head < tail && que[head].pos < k - num)head++;//限长度 while(head < tail && que[tail - 1].value <= y)tail --; que[tail].value = y; que[tail].pos = x; tail ++; dp[k * c[i] + mo] = que[head].value + k * w[i]; //加上k * w[i]的原因:单调队列维护的是前i - 1中的状态最大值 //因此这里加上 } }
}```