目录
零. dp 分析
- 状态表示
- 集合：所有…的集合
- 条件：边界、前几个、后几个、体积小于…、时间小于…等（集合的设计带来的一些边界条件）
- 属性：max、min ......（状态表示了这个集合的什么值？与状态转移相区别）
- 集合：所有…的集合
- 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。
一. 分析
- 01背包中：
f[i][j]可以划分为第 i 个物品选还是不选，分别对应之前的两个状态，从而可以转台转移和计算 - 完全背包：假设容积 j 可以容纳至多 k 个第 i 个物品，那么
f[i][j]可以划分为第 i 个物品拿 $[0, k]$ 个，总计 $k + 1$ 个状态，即下方所示。因此理所当然的可以想到对f[i][j]的计算应循环 $k + 1$ 次，那么就是三重循环，当 container = 1000, vol[i] = 1 时，时间复杂度可以达到 $O(10^{9})$ 超时，因此优化状态转移，即f[i][j] = max(f[i-1][j], f[i][j-vol[i]] + val[i])。 - 多重背包Ⅰ：容积 j 可以容纳至多 k 个第 i 个物品，第 i 个物品总共 num[i] 个，综合这两个限制，假设第 i 个物品最多拿
x = min(k, num[i])个。那么f[i][j]可以划分为第 i 个物品拿 $[0, x]$ 个，总计 $x + 1$ 个状态。区别于完全背包，多重背包中，状态f[i][j]和状态f[i][j-vol[i]]之间联系更加复杂，即f[i][j]和f[i][j-vol[i]]可能选用不同的数量来分别得到其最大值，因此之前的优化状态转移不再适用，即要使用完全背包的朴素解法。注意：f[i][j]拿了 x 个第 i 个物品（x 为上述假设的最大数量），f[i][j+1]仍有可能拿 x 个第 i 个物品.f[i][...]含义：要计算拿几个第 i 个物品，可以使从相应的f[i-1][...-(几个*vol[i])]状态转移过来后，可以取得最大值。即，f[i][...]都是从对应方案的f[i-1][...]转移过来的f[i][j]和f[i][j-vol[i]]可能选用不同的数量来分别得到其最大值，因此不能用f[i][j] = max(f[i-1][j], f[i][j-vol[i]] + val[i])来计算f[i][j]
- 多重背包Ⅱ：题目主要考察多重背包的二进制优化。数据范围增大，朴素的三重循环解决多重背包的方法一定会超时，因此要寻求优化。在上一篇多重背包的题解中，已经分析了通过状态转移优化计算已经不可能。因为可能选取完全不同的方案（我之前的理解不够彻底）。前提同上：容积 j 可以容纳至多 k 个第 i 个物品，第 i 个物品总共 num[i] 个，综合这两个限制，假设第 i 个物品最多拿
x = min(k, num[i])个。那么f[i][j]可以划分为第 i 个物品拿 $[0, x]$ 个，总计 $x + 1$ 个状态。区别于完全背包的状态转移，这里的 x < k 且当 j 足够大时，就会导致f[i][j-vol[i]]的状态转移中的最后一项不在f[i][j]的状态转移范围之内。而求出f[i][j-vol[i]]之后，没有办法求去除最后一项的 max 值（或者很难），因此导致无法通过优化状态转移来计算。具体请见， AcWing 5. 多重背包问题 II 二进制优化 - 多重背包Ⅲ：单调队列优化。 有了前面的铺垫，这里只不过是使用了一个多重背包Ⅱ中说的“求去除最后一项的 max 值”的方法来优化求解过程。通过前面的分析可知，
f[i][j-vol[i]]的状态转移方程中包含了一项在f[i][j]的状态转移方程中没有包含的项（简称为多余项），才导致的无法求解。但是f[i][j]和f[i][j-vol[i]]仍然有大量的相同的项。如果在求f[i][j-vol[i]]时保留多余项，之后求f[i][j]时，去除多余项再求max，并在求解过程中一直维护状态之间的共同项，是否也能高效的求解？（废话，但是问题是，如何分析这种优化解法的时间复杂度？）
二. 单调队列优化
单调队列例题：AcWing 154. 滑动窗口 。
- 通过上述分析可知，要维护状态之间的共同项（这些状态转移方程中的共同项不难发现一定是相邻的，即其相邻状态值只差个
val[i]），并且最终目的是求其中的最大值，因此可以联想到单调队列。 - 在使用单调队列维护这些值时，有一些注意事项：
f[i][j]和f[i][j-1]（或者和f[i][j+1]）的状态转移方程中可能没有共同项（当vol[i] = 1的时候就有共同项了，当然这里只是意在说明哪些状态之间有联系，可以使用单调队列来维护一个最大值）。从之前的状态转移方程中可以发现，f[i][j]只有和f[i][j-vol[i]]有共同项。（或f[i][j+vol[i]]，甚至f[i][j+some_number * vol[i]]都可能有共同项。当然离得远了之后，这和这题没什么关系了）- 因此本题遍历容积 j 时，不能再像之前那样（因为只对一系列有关的状态维护一个单调队列）。本题采用的方法是：$余数 j\in [0, vol[i]] \quad$ ，同时递增的 $step = vol[i]$。
- 单调队列的维护：参考AcWing 154. 滑动窗口 。具体对于本题而言：
- 当队头元素比状态转移方程中最靠前的状态还要靠前，那么就要出队。
- 先计算当前状态
f[i][j]之后再更新队列（根据状态转移方程得出，f[i][j]和之前的状态，以及f[i-1][j] (代表了不拿第 i 个物品)有关系） - （Trick）单调队列的维护技巧。从之前的状态转移方程中（具体请见， AcWing 5. 多重背包问题 II 二进制优化 ），计算
f[i][j]和f[i][j-vol[i]]时，两个状态转移方程中每个对应的旧的状态所加的 $value$ 值是不同的。对于具有相同余数的状态（即上述的本题的遍历序列中），计算每个f[i][j]时前面某一个固定状态f[i-1][j-k*vol[i]]所要加的 $value$ 值不同，且对于f[i-1][j-k*vol[i]]，f[i][j]越靠后f[i-1][j-k*vol[i]]所要加的值越大。每到一个状态就重新计算队列中的值是比较复杂的。- 对此解决办法是：单调队列只存旧状态的值，即对应的
f[i-1][j-k*vol[i]]的值，计算f[i][j]时加上对应的 $value$ 值即可。 - 对于单调队列的维护（即对于不同 $k$ 的
f[i-1][j-k*vol[i]]哪些应该留在单调队列里）：虽然计算每个f[i][j]时，f[i-1][j-k*vol[i]]应加的 $value$ 值不同，但是对于任何一个f[i][j]的计算，其状态转移方程中相邻旧状态之间永远只差一个 $val[i]$（同样是越靠前的，应加的$val[i]$个数越多，越靠后的越少）。不妨从计算最后一个状态的状态转移方程中看，可以把余数为 j 的遍历序列中涉及的所有旧状态的第一个加上最大的 $value$ ，并之后依次递减，同时存储进单调队列时不存这个加上的值，只存旧状态的值，那么此时方便比较和维护了。但是最多应该加几个$val[i]$不方便计算，反正每个相邻的旧状态都只差一个$val[i]$，因此可以考虑第一个旧状态减去0，第二个减去$val[i]$，第三个减去$2\times val[i]$，以此类推，离前面的越远减去的值越多，同样可以起到相同的效果，同时免去了计算加几个的问题。
- 对此解决办法是：单调队列只存旧状态的值，即对应的
- 要求的是最大值。因此单调队列应维护一个最大值（降序）的单调队列。
三. 代码
技巧：
- 滚动数组，免去了复制数据的时间开销。
vol[i]和val[i]没有像之前一样再开数组：节省空间，降低空间复杂度。
能用一个数组实现吗？答：能，但是应该很麻烦。首先可能得逆序遍历余数为 j 的状态序列。单调队列的计算是需要正序的，因此要提前正序遍历一遍余数为 j 的状态序列，用栈或者什么数据结构记录下来对应的最值。逆序遍历用之前记录的值直接更新。虽然免去了一维数组，但是要存储单调队列的值，要增加空间开销，不一定比原来一个数组小。而且实现难度增加，浪费时间，debug 更复杂。因此实现这个没必要，考场上也不现实。
#include<iostream>
#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rep_gt(i, a, b) for(int i = (b); i > (a); -- i)
#define _rep_le_step(i, a, b, step) for(int i = (a); i <= (b); i += (step))
using namespace std;
const int N = 2e4 + 5;
/**
* f: indicates state of dp
* q: motonic queue (descend)
* qh: motonic queue's head
* qt: motonic queue's tail
* (qt < qh): queue is empty
*/
int f[2][N], q[N];
int qh, qt;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int number = 0, container = 0;
cin >> number >> container;
_rep_le(i, 1, number) {
// First i items
int vo = 0, va = 0, num = 0;
cin >> vo >> va >> num;
_rep_lt(j, 0, vo) {
// Remainder ([0, vo - 1])
qh = 0, qt = -1;
_rep_le_step(k, j, container, vo) {
/**
* For states with same remainder,
* the minimum value in the states transition equation
* can be maintained with a motonic queue.
*/
// Get current array which will be calculated
int cur = i & 1;
// Last array indicates f[i-1][...]
int last = cur ^ 1;
// Head element is out the range of state transition equation
if(qh <= qt && q[qh] < k - num * vo) qh ++;
// Calculate f[cur][k] which indicates f[i][j] using motonic queue's head element
// Value should be added is that: value = (k - q[qh]) / vol[i] * val[i]
if(qh <= qt) f[cur][k] = max(f[last][k], f[last][q[qh]] + (k - q[qh]) / vo * va);
// Delete invalid value by deleting tail element of motonic queue
// Expect the maximum value, so remove smaller values during maintenance
/**
* From analysis, use (q[qt] - j) (for q[qt]) or (k - j)(for current k)
* to measure the number of val[i] that should be subtracted.
*/
while(qh <= qt &&
(f[last][q[qt]] - (q[qt] - j) / vo * va) <= (f[last][k] - (k - j) / vo * va)) qt --;
// Enqueue the current k to approriate location
qt ++;
q[qt] = k;
}
}
}
// Output the value where last operation was stored
cout << f[number & 1][container] << endl;
return 0;
}
