这道题可以直接看做是多重背包问题III
当s=-1时,令s=1
当s=0时,令s=m/v,因为不能超过背包容量
接下来直接套模板
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int f[N], g[N];
int q[N];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
int v, w, s;
cin >> v >> w >> s;
if (s == -1) s = 1;
else if (s == 0) s = m / v;
memcpy(g, f, sizeof g);
for (int r = 0; r < v; r ++)
{
int tt = -1, hh = 0;
for (int j = r; j <= m; j += v)
{
if (tt >= hh && q[hh] < j - s * v) hh ++;
while (tt >= hh && g[j] >= g[q[tt]] + (j - q[tt]) / v * w) -- tt;
q[++ tt] = j;
f[j] = g[q[hh]] + (j - q[hh]) / v * w;
}
}
}
cout << f[m] << endl;
return 0;
}