多重背包 (单调队列)

题目链接

#include <bits/stdc++.h>
using ll = long long;
const int N = 1E3 + 5 , M = 2E4 + 5;

int n,m;
int v[N],w[N],s[N];
int f[M];
int l,r,q[M];

int calc(int i,int u,int k) {
	return f[k * v[i] + u] - k * w[i];
}

int main() 
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	std::cin >> n >> m;
	for (int i = 1 ; i <= n ; ++i) {
		std::cin >> v[i] >> w[i] >> s[i];
	}
	
	for (int i = 1 ; i <= n ; ++i) 
	{
		for (int u = 0 ; u < v[i] ; ++u)
		{
			//j = p * v[i] + u;
			//_j = k * v[i] + u;
			// f[j] = max{f[_j] + (p - k) * w[i]}; 
			//处理出 f[k * v[i] + u] - k * w[i] 与 k 相关 
			//预处理队列内容 
			int maxp = (m - u) / v[i];
			l = 1 , r = 0;//队列要求下标递减 
			for (int k = maxp - 1 ; k >= std::max(maxp - s[i] , 0) ; --k) {
//				while (l <= r && q[l] > maxp - 1) ++l; 在这里没有必要 
				while (l <= r && calc(i , u , q[r]) <= calc(i , u , k)) --r;
				q[++r] = k;
			} 
			
			for (int p = maxp ; p >= 0 ; --p) 
			{
				while (l <= r && q[l] > p - 1) ++l;
				
				if (l <= r)
					f[p * v[i] + u] = std::max(f[p * v[i] + u] , calc(i , u , q[l]) + p * w[i]);
					
				//为下一个集合的扩展一位 
				if (p - s[i] - 1 >= 0) {
					while (l <= r && calc(i , u , q[r]) <= calc(i , u , p - s[i] - 1)) r--;
					q[++r] = p - s[i] - 1;
				}
			}
			
		}
	}
	
	int ans = 0;
	for (int i = 0 ; i <= m ; ++i)
		ans = std::max(ans , f[i]);
	std::cout << ans << '\n';
	
	return 0;	
}