洛谷-P1776 宝物筛选(单调队列优化多重背包)¶
题目描述¶
终于,破解了千年的难题。小 FF 找到了王室的宝物室,里面堆满了无数价值连城的宝物。
这下小 FF 可发财了,嘎嘎。但是这里的宝物实在是太多了,小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。
小 FF 对洞穴里的宝物进行了整理,他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值,之后开始了宝物筛选工作:小 FF 有一个最大载重为 W*W* 的采集车,洞穴里总共有 n*n* 种宝物,每种宝物的价值为 v_i*v**i*,重量为 w_i*w**i*,每种宝物有 m_i*m**i* 件。小 FF 希望在采集车不超载的前提下,选择一些宝物装进采集车,使得它们的价值和最大。
输入格式¶
第一行为一个整数 n*n* 和 W*W*,分别表示宝物种数和采集车的最大载重。
接下来 n*n* 行每行三个整数 v_i,w_i,m_i*v**i*,w**i,m**i。
输出格式¶
输出仅一个整数,表示在采集车不超载的情况下收集的宝物的最大价值。
输入输出样例¶
输入 #1
4 20
3 9 3
5 9 1
9 4 2
8 1 3
输出 #1
47
说明/提示¶
对于 30\%30% 的数据,n\leq \sum m_i\leq 10^4*n*≤∑m**i≤104,0\le W\leq 10^30≤W≤103。
对于 100\%100% 的数据,n\leq \sum m_i \leq 10^5*n*≤∑m**i≤105,0\le W\leq 4\times 10^40≤W≤4×104,1\leq n\le 1001≤n≤100。
#include <bits/stdc++.h>
using namespace std;
vector<int> price(105), value(105), num(105);
int n, m;
vector<int> dq_pos(40005), dq_val(40005); //模拟双端队列
vector<int> d(40005);
int multiPack()
{
for (int i = 0; i < n; ++i) {
for (int a = 0; a < price[i]; ++a) {
int start = 0, end = 0;
for (int j = 0; a + j * price[i] <= m; ++j) {
int tmp = d[a + j * price[i]] - j * value[i];
while (start < end && dq_val[end - 1] <= tmp) --end;
dq_pos[end] = j;
dq_val[end++] = tmp;
d[a + j * price[i]] = dq_val[start] + j * value[i];
if (dq_pos[start] == j - num[i]) ++start;
}
}
}
return d[m];
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> value[i] >> price[i] >> num[i];
cout << multiPack() << endl;
return 0;
}