[牛客竞赛]蕾凹娜的哀伤（多重背包DP + 二进制优化）

题目传送门：A-蕾凹娜的哀伤_喜迎暑假多校联赛第二场（欢乐AK找回自信） (nowcoder.com)

题意 / Problem

中文题意不解释了。

思路 / Thought

多重背包问题，加上二进制优化后复杂度为O(N * V * log(S))。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e4 + 5;
int dp[maxn];//dp[i] means the Worth could get by Volume i.

signed main()
{
	ios::sync_with_stdio(false);
	int N, V;cin >> N >> V;//the count of Items and the Volume of bag.
	for(int i = 1;i <= N; ++ i)
	{
		int t, w, s;//the Volume, Worth and Count of Items.
		cin >> t >> w >> s;
		//二进制分解
		for(int j = 1;j <= s; s -= j, j <<= 1)//the count of items buy once.
			for(int k = V;k >= j * t; -- k)//remember Traverse from back to front
				dp[k] = max(dp[k], dp[k - j * t] + j * w);

		if(s)//the remainder of items should be calculate too.
		{
			for(int k = V;k >= s * t; -- k)//remember Traverse from back to front
				dp[k] = max(dp[k], dp[k - s * t] + s * w);
		}
	}
	cout << *max_element(dp + 1, dp + 1 + V) << '\n';
	return 0;
}