首先說一些寫本文時的悲慘經歷，一開始我是使用 Gridea，編輯也是用它的編輯器，但是，在一次寫作中，電腦無徵兆地藍屏了。我重啟之後發現 md 文件打不開了，查看了一下二進制全是 0 emmm（編寫過程中保存了！！）。自此我換成了 hexo emmm。
符號定義#
首先我們定義一些符號，物品個數為 $n$ ，
第 $i$ 個物品的體積為 $v_i$ ，價值為 $w_i$ , 最多為 $s_i$ 個。
背包的體積為 $V$，動歸數組為 $dp$ 。
回顧#
我們先回顧多重背包的優化，（ $x$ 是 背包體積為 $j$ 時，背包能夠承受的最大個數，即 $j /v$）
設此時第 $i$ 個物品的體積為 $v$ 。
dp[i, j]= max(dp[i - 1, j], dp[i - 1, j - v] + w, dp[i - 1, j - 2v] + 2w, ......,dp[i - 1, j - (x - 1) v] + (x - 1)w, dp[i - 1, j - xv] + xw)
然後我們來思考，完全背包時，$dp [i,j]$ 和 $dp [i,j - v]$ 的聯繫
dp[i, j - v]= max(dp[i - 1, j - v], dp[i - 1, j - 2v] + w, dp[i - 1, j - 3v] + 2w, ......, dp[i - 1, j - (x - 1) v] + (x - 2)w, dp[i - 1, j - xv] + (x - 1)w)
（有的同學可能會問最後一個背包能承受的數量為什麼還是 $x$ ，但其實那不是 $x$ ，是 $ j-v-(\frac {j-v}{v}) v$ 算出來狀態最終減的是 $xv$ ）
然後我們驚奇地發現， $max ()$ 第一項之後的 和 $dp [i,j - v]$ 是如此的相似，只差了個 $w$ ，所以我們可以把 $w$ 移出來，替換成
dp[i, j]= max(dp[i - 1, j], dp[i][j - v] + w)
否定#
然後我們來看多重背包，我們還推柿子看看（我們先假設此時 $j$ 遠大於 $sv$ ）
我們先嘗試能否用完全背包的方法來優化，
dp[i, j]= max(dp[i - 1, j], dp[i - 1, j - v] + w, dp[i - 1, j - 2v] + 2w, ......,dp[i - 1, j - (s - 1) v] + (s - 1)w, dp[i - 1, j - sv] + sw
dp[i, j - v]= max(dp[i - 1, j - v], dp[i - 1, j - 2v] + w, dp[i - 1, j - 3v] + 2w, ......, dp[i - 1, j - (s - 1) v] + (s - 2)w, dp[i - 1, j - sv] + (s - 1)w)
看起來似乎很對，是嗎？（
但是我們考慮一下項數，我們會發下 $dp [i, j-v]$ 的項數 和 $dp [i,j]$ 相同，都是 $s$ 項 ，不和 $max ()$ 第一項之後的 項數相同，從而不能使用之前的方法優化
展新#
（從這一小節開始用一維數組，方便表示，沒學過一維數組表示的去學一下 ）
我們還是考慮 $dp [j]$，還是列柿子
dp[j]= max(dp[j], dp[j - v] + w, dp[j - 2v] + 2w, ......,dp[j - (s - 1) v] + (s - 1)w, dp[j - sv] + sw
我們觀察這個柿子，很容易得出一個性質，會更新狀態 $j$ 的狀態和 $j$ 都是模 $v$ 意義下同餘的。於是我們把狀態 $1$ 到 $V$ 劃分成 $v$ 類，分別是模 $v$ 余 $0$ 的，模 $v$ 余 $1$ 的，$\cdots$，模 $v$ 余 $v-2$ 的，以及模 $v$ 余 $v-1$ 的。
原來的dp[1]~dp[V]我們就可以變化成這 $v$ 類（這裡比較難想，但一定要想明白）
dp[0] dp[v] dp[2v] dp[3v] ... dp[kv]
dp[1] dp[1+v] dp[1+2v] dp[1+3v] ... dp[1+kv]
dp[2] dp[2+v] dp[2+2v] dp[2+3v] ... dp[2+kv]
...
dp[v-1] dp[v-1+v] dp[v-1+2v] dp[v-1+3v] ... dp[v-1+kv]
然後我們就可以在這 $v$ 類分別更新了。（其中 $... + kv$ 為恰好滿足最後一個狀，看代碼）
寫一下這樣的代碼（先寫一個二維的）（如果改為一維要倒序枚舉狀態或利用滾動數組）
for(int i = 1;i <= n;i++)
{
for(u = 0;u < v[i];u++)
{
for(int k = 0;u + k * v[i] <= V;k++)
{
int e = u + k * v[i];
for(int t = min(k - s * v[i], u)/*防止減到負數*/;t < k;t += v[i])
{
dp[i][e] = max(dp[i - 1][e], dp[i - 1][t] + (e - t) / v[i] * w[i]);
}
}
}
}
對，你沒有看錯，這是四層循環，也許你要問了，這循環怎麼還越搞越多了，但是讓我們分析一下他的時間複雜度。第一層循環 $O (n)$，第二層循環是枚舉每一類的起始值的，第三層是枚舉該類裡每一個狀態的，二三層的總共時間複雜度是 $O (V)$，最後一層就是枚舉 可以轉移到當前狀態的狀態，是 $O (s)$ 的，所以總共時間複雜度還是 $O (nVs)$ 的。
如果上面沒明白我們舉個例子。
舉個例子吧，假設有 $2$ 件物品，$v_1 = 5$，$w_1 = 6$，$s_1 = 3$，$v_2 = 4$，$w_2 = 8$，$s_2 = 5$，背包體積為 $31$
在 $i = 1$ 即枚舉第一個物品的時候，dp 狀態的分類為
dp[0] dp[5] dp[10] dp[15] dp[20] dp[25] dp[30]
dp[1] dp[6] dp[11] dp[16] dp[21] dp[26] dp[31]
dp[2] dp[7] dp[12] dp[17] dp[22] dp[27]
dp[3] dp[8] dp[13] dp[18] dp[23] dp[28]
dp[4] dp[9] dp[14] dp[19] dp[24] dp[29]
//第一（余數為0）的一類
dp[1][0] = dp[0][0]
dp[1][5] = max(dp[0][5], dp[0][0] + w[1])
dp[1][10] = max(dp[0][10], dp[0][5] + w[1], dp[0][0] + 2 * w[1])
dp[1][15] = max(dp[0][15], dp[0][10] + w[1], dp[0][5] + 2 * w[1], dp[0][0] + 3 * w[1])
dp[1][20] = max(dp[0][20], dp[0][15] + w[1], dp[0][10] + 2 * w[1], dp[0][5] + 3 * w[1])
//最多選3個，所以最多體積（第二維）最多減3個v[i]
dp[1][25] = max(dp[0][25], dp[0][20] + w[1], dp[0][15] + 2 * w[1], dp[0][10] + 3 * w[1])
dp[1][30] = max(dp[0][30], dp[0][25] + w[1], dp[0][20] + 2 * w[1], dp[0][15] + 3 * w[1])
//下同
$i = 2$ 也一樣
單調隊列優化#
也許你要問了，說了這麼多怎麼連單調隊列的影子都沒看見，其實我們之前做的都是為了 ta 做鋪墊，ta 這不就來了。
首先，我們要優化的就是上面的代碼的第四層：由當前狀態的前面 $s$ 個（不相鄰的，每兩個相差 $v$）狀態來更新當前狀態。
我們從感性地角度來思考一下，上圖！（qwq
我們來看這個圖， $j$ 這裡表示的就是當前狀態 ，$j'$ 表示的是下一個狀態 即 $j + v$，灰色格子表示的是 *** 可以更新當前狀態（這裡為 $j$ 或 $j'$）*的狀態
！！！！！注意：圖片裡第一行最左面的應該是 $j-sv$ 手癢寫錯了（懶得改了 emmm）
我們可以觀察出來，狀態每增加 $v$ ta 的式子dp[j]= max(dp[j], dp[j - v] + w, dp[j - 2v] + 2w, ......,dp[j - (s - 1) v] + (s - 1)w, dp[j - sv] + sw就會失去最後（圖上最左）面的一个 可以更新 ta 的狀態 ，同時也得到了最前（圖上最右）面的一个 可以更新 ta 的狀態。
讓我們思考一下，可以在兩端插入（因為 $j$ 每次增加 $v$，max 函數每就會多一個可用來更新 當前狀態 $j$ 的狀態），刪除數據（也會少一個），並支持較小 （$O (1)$）的時間複雜度求最大值（為 max 函數要求）的數據結構是什麼？單調隊列！(單調隊列裡存的是下標，而不是具體數據)
一些小細節#
偏移量#
dp[0] dp[v] dp[2v] dp[3v] ... dp[kv]
dp[1] dp[1+v] dp[1+2v] dp[1+3v] ... dp[1+kv]
dp[2] dp[2+v] dp[2+2v] dp[2+3v] ... dp[2+kv]
...
dp[v-1] dp[v-1+v] dp[v-1+2v] dp[v-1+3v] ... dp[v-1+kv]
我們把類的起點（指dp[0]到dp[v-1]），隨便選一個，設為 $u$ 來看。
dp[u] = dp[u]
dp[u+v] = max(dp[u] + w, dp[u + v])
dp[u+2v] = max(dp[u] + 2w, dp[u + v] + w, dp[u + 2v])
dp[u+3v] = max(dp[u] + 3w, dp[u + v] + 2w, dp[u + 2v] + w, dp[u + 3v])
...
我們發現在 max 函數裡，dp [] 後面加的值不一樣，這就很受傷，我們在單調隊列裡更新值很不方便，所以我們搞點花樣。
dp[u] = dp[u]
dp[u+v] = max(dp[u], dp[u + v] - w) + w
dp[u+2v] = max(dp[u], dp[u + v] - w, dp[u + 2v] - 2w) + 2w
dp[u+3v] = max(dp[u], dp[u + v] - w, dp[u + 2v] - 2w, dp[u + 3v] -3w) + 3w
...
這樣看起來就很舒服了。每次進單調隊列的值就是dp[u + kv] - k*w。更新當前狀態的時候最後別忘了加上 $a\times w$ ，a 就是 $（當前狀態 - 隊首狀態）/v$。為什麼呢，我們來看一看
我們知道，隊首dp[u + kv] - k*w為 $u$ 固定，$k$ 在範圍內任意取得的最大值。我們在更新當前狀態 (假設為 $u + bv$) 的時候 ，max 函數外的偏移量為 正的 $bv$ ，而dp[u + kv]比dp[u + kv] - k*w少減了 $kw$ ，而最後 max 函數外又要給 ta 加上 $bv$ ，所以綜合下來就是加上 $(b - k) * w$ 也就是 $（當前狀態 - 隊首狀態）/v * w$
隊列裡個數應為 $s+1$ 個，為 $0$ 到 $s$ 個 前面狀態
滾動數組#
前面提到過，多重背包要麼倒序枚舉，要麼滾動（備份）數據，但單調隊列的性質來看，倒序枚舉不太方便，所以我們採用備份數組的方式
代碼#
然後我們就可以愉快地敲代碼了
#include<iostream>
#include<cstdlib>
#include<cstring>//memcpy函數需要的頭文件
using namespace std;
const int N = 200005;
int q[N];//單調隊列，實際存的是下標
int g[N];//備份數組
int dp[N];
int main()
{
int n, V;
cin >> n >> V;
for(int i = 1;i <= n;i++)
{
int v, w, s;//可以選擇邊讀入邊計算，就可以不用創建數組了
memcpy(g, dp, sizeof dp);//備份
cin >> v >> w >> s;
for(int u = 0;u < v;u++)//枚舉每一類的起點
{
int hh = 0, tt = -1;//因為單調隊列這選擇維護的是一個閉區間，如果tt也等於1
//表示的就是有一個元素了qwq
for(int k = u;k <= V;k += v)//這裡的k含義和上面有所區別
{
while(hh <= tt && (k - q[hh]) > s * v) hh++; //超出s就彈出
while(hh <= tt && g[q[tt]] - (q[tt] - u) / v * w < (g[k] - (k - u) / v * w)) tt--;//保持隊列單調
q[++tt] = k;//把當前狀態放入
if(hh <= tt) dp[k] = max(dp[k], g[q[hh]] + (k - q[hh]) / v * w);//更新當前狀態
}
}
}
cout << dp[V];
return 0;
}
完結撒花！