题目描述

https://www.acwing.com/problem/content/6/

单调队列优化+滚动数组优化

根据yxc大佬的讲解

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int n,m;
int v[maxn],w[maxn],s[maxn],f[maxn][maxn];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s[i] && j-k*v[i]>=0;k++)
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout<<f[m]<<endl;
}

首先优化思路来自最最原始的无优化的方程。
仔细观察，对于任意的j，都是从v[i]的倍数转移过来的。它们本来应该是连续的，可以用滑动窗口（不熟悉此问题的同学可以先行百度）解决。但在无优化的时候却每次把所有的倍数都遍历了一遍。
所以可以把m根据模v[i]的余数分为v[i]类。

for(int j=0;j<v;j++)

此时对于任意的j，只需要向v[i]的倍数去转移。所以我们在下一层循环的时候把k定义为j+k*v[i]

for(int k=j;k<=m;k+=v)

此时的k相当于原来的j，但是我们可以利用k和v之间存在的倍数关系去做滑动窗口。
由于滑动窗口记录的是下标，但每一个k所对应的下标都是在变化的。所以要根据当前的k判断窗口里存在的k对应的值包含了多少个v，以便于计算新的价值

v的个数=(下标-余数)/v   价值=(下标-余数)/v*w
       =(q[h]-j)/v          =(k-j)/v*w

然后每次只用了前i-1的值，所以可以滚动数组优化一下空间

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[20002],q[20002],g[20002];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(g,f,sizeof(f));
        //滚动数组优化空间，g[]即f[i-1][];
        for(int j=0;j<v;j++)
        {
            int hh=0,tt=-1;
            for(int k=j;k<=m;k+=v)
            {
                f[k]=g[k];
                if(hh<=tt && k-s*v>q[hh])  
                //如果当前窗口的内容超过了s个;
                {
                    hh++;
                }
                if(hh<=tt) 
                {
                    f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w); 
                    //max(f[i-1][k],f[i-1][能转移里最大]+个数*v[i]);
                }
                while(hh<=tt && g[q[tt]]-(q[tt]-j)/v*w <= g[k]-(k-j)/v*w)
                {
                    tt--;
                }
                q[++tt]=k;
            }
        }
    }
    cout<<f[m]<<endl;
}