题目传送门: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; }
Comments NOTHING