对单调队列优化的一些理解

变量定义

令背包体积为c,循环时体积为j,当前物品的体积为v,价值为w,数量为s. 需计算dp[0,c]的值

理解

根据状态转移方程 dp[i][j] = max(dp[i - 1][j - k * (v)] + k * w) 0<=k<=s (此处不考虑体积不足情况)
可知dp[j]是由 间隔为 v 的值转移过来的.
那么根据j%v的余数划分等价类,dp[j]就只能由同一等价类转移过来
(依靠划分等价类将不相邻的区间,变成逻辑相邻的区间,就可以套用单调队列进行优化)
由
dp[i][j   ] = max{                               dp[i-1][j]   , dp[i-1][j-v]+ w, dp[i-1][j-2v]+2w......dp[i-1][j-(k-2)v]+(k-2)w, dp[i-1][j-(k-1)v]+(k-1)w, dp[i-1][j-kv]+kw}; 
dp[i][j+ v] = max{               dp[i-1][j+v]  , dp[i-1][j]+ w, dp[i-1][j-v]+2w, dp[i-1][j-2v]+3w......dp[i-1][j-(k-2)v]+(k-1)w, dp[i-1][j-(k-1)v]+(k  )w                  };
dp[i][j+2v] = max{dp[i-1][j+2v], dp[i-1][j+v]+w, dp[i-1][j]+2w, dp[i-1][j-v]+3w, dp[i-1][j-2v]+4w......dp[i-1][j-(k-2)v]+(k  )w                                            };
可知:
    越靠前的项增加的w越多
    j每增加一个v时,原集合所有元素需增加一个w
    可以运用滑动窗口,单调队列解决

    如何解决每次增加w问题?
    我们只需知道哪项最大,单调队列可以只用维护相对大小.
将j离t（令t同一等价类首元素）越近增加的w越多。每多间隔一个v，增加会少一个w。
转化为，离f越近减去w越少，减少（（j - t）/ v）个 w。
那么同一集合元素其相对大小不变。例子如下:
令v = 3, s = 3可知
f[0 ] = f[0 ]
f[ v] = f[ v], f[0 ]+w
f[2v] = f[2v], f[ v]+w, f[0 ]+2w
f[3v] = f[3v], f[2v]+w, f[ v]+2w, f[0]+3w
f[4v] = f[4v], f[3v]+w, f[2v]+2w, f[v]+3w

令
f[0 ] = f[0 ]
f[ v] = f[ v] - 1w
f[2v] = f[2v] - 2w
f[3v] = f[3v] - 3w
f[4v] = f[4v] - 4w

则原式变化为
f[0 ] = f[0 ]
f[ v] = f[ v]- w, f[0 ]
f[2v] = f[2v]-2w, f[ v]- w, f[0 ]
f[3v] = f[3v]-3w, f[2v]-2w, f[ v]- w, f[0]
f[4v] = f[4v]-4w, f[3v]-3w, f[2v]-2w, f[v]-w

对比
f[3v] = f[3v]   , f[2v]+ w, f[v]+2w, f[0]+3w
f[3v] = f[3v]-3w, f[2v]-2w, f[v]- w, f[0]
可得:f[3v]对应状态集合中的相对大小并未改变

//先放上yxc大佬代码 1000ms左右
#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
int n, m;
int dp[N], g[N], q[N];

int main(){
    cin>>n>>m;
    for(int i=1; i<=n; ++i){
        int v, w, s; cin>>v>>w>>s;
        memcpy(g, dp, sizeof(dp));

        //g为dp[i-1], dp为dp[i]
        for(int j=0; j<v; ++j){//枚举余数即等价类
            int hh = 0, tt = -1;//hh为队首 tt为队尾
            for(int k=j; k<=m; k+=v){//枚举同一等价类的背包体积
                dp[k] = g[k]; //此句意义不大，
                if(hh <= tt && k - s * v > q[hh]) ++hh;//弹出首部（该首部为不合法信息）
                /*
                    tt >= hh 是单调队列非空成立条件
                    k - s * v > q[hh]
                    该单调队列要维护一个不超过s的集合。
                    如果当前编号-队列最大容积（间隔v 容积s * v）＞首元素，则需将首元素出队
                */
                if(hh <= tt) dp[k] = max(dp[k], g[q[hh]]+(k - q[hh]) / v * w);//更新当前数
                /*
                    首元素是放置物品中的最大，需要和不放物品值进行比较
                    q队列实际放的是位置，位置差比上v就是放置物品的数量
                */
                while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) --tt;//弹出小于元素
                /*
                   （编号-j）/ v * w是上面转化的条件
                */
                q[++tt] = k;//将当前数插入队列
                /*
                   插入队列的实际是位置而不是数值
                   因为我们还需要位置差信息
                */
            }
        }
    }
    cout<<dp[m]<<endl;
}

// 讨论区Belous大佬的代码 380ms
#include <stdio.h>
const int  N  = 20001;
struct node{
    int pos, val;
}q[N];
int dp[N];
int main(){
    int n, m; scanf("%d%d", &n, &m);
    while (n--){
        int v, w, s; scanf("%d%d%d", &v, &w, &s);
        for (int j = 0; j < v; ++j){
            int hh = 0, tt = 0, stop = (m - j) / v;
            //[hh, tt)
            for (int k = 0; k <= stop; ++k){
                int val = dp[k * v + j] - k * w;
                while (hh < tt && val >= q[tt-1].val) --tt;
                q[tt].pos = k, q[tt++].val = val;
                if (q[hh].pos < k - s) ++hh;
                dp[v * k + j] = q[hh].val + k * w;
            }
        }
    }
    printf("%d\n", dp[m]);
}

如果有优于380ms的代码(裸单调队列优化)欢迎留言