http://codevs.cn/problem/5429 /
把背包体积按 模物品体积 分类
在每个剩余类中使用单调队列
具体点就是
设物品体积为 v, 价值为 w, 现在要计算体积模 v=0 时的价值
设 f[i][j] 表示 前 i 个物品, 体积为 j 时的最大价值
f[i][5v]=max{f[i-1][4v]+w , f[i-1][3v]+2w , f[i-1][2v]+3w , f[i-1][v]+4w , f[i-1][0]+5w }
f[i][4v]=max{f[i-1][3v]+w , f[i-1][2v]+2w , f[i-1][v]+3w , f[i-1][0]+4w }
对所有的 f[i][j]-j/v*wf[i][5v]=max{f[i-1][4v]-4w , f[i-1][3v]-3w , f[i-1][2v]-2w , f[i-1][v]-w , f[i-1][0] }f[i][4v]=max{f[i-1][3v]-3w , f[i-1][2v]-2w , f[i-1][v]-w , f[i-1][0] } 即 f[i][j]=max{f[i-1][j%v k*v]-k*w}+j*w 当固定了 j%v 后, 就可以使用单调队列优化了
#include < cstdio > using namespace std;
int dp[7001];
int q[7001][2];
int main() {
int n,
m;
scanf("%d%d", &n, &m);
int v,
w,
cnt;
int h,
t;
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &v, &w, &cnt);
if (m / v < cnt) cnt = m / v;
for (int j = 0; j < v; ++j) {
h = 0;
t = 0;
for (int k = 0; k <= (m - j) / v; ++k) {
while (h < t && dp[j + k * v] - k * w > q[t - 1][0]) t--;
while (h < t && q[h][1] + cnt < k) h++;
q[t][0] = dp[j + k * v] - k * w;
q[t++][1] = k;
dp[j + k * v] = q[h][0] + k * w;
}
}
}
printf("%d", dp[m]);
}
来源: http://www.bubuko.com/infodetail-2481333.html