P1776 宝物筛选_NOI导刊2010提高(02)[dp+单调队列]

题目描述

终于,破解了千年的难题。小FF找到了王室的宝物室,里面堆满了无数价值连城的宝物……这下小FF可发财了,嘎嘎。但是这里的宝物实在是太多了,小FF的采集车似乎装不下那么多宝物。看来小FF只能含泪舍弃其中的一部分宝物了……小FF对洞穴里的宝物进行了整理,他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值,之后开始了宝物筛选工作:小FF有一个最大载重为W的采集车,洞穴里总共有n种宝物,每种宝物的价值为v[i],重量为 w[i],每种宝物有$m_i$件。小FF希望在采集车不超载的前提下,选择一些宝物装进采集车,使得它们的价值和最大。

输入输出格式

输入格式:

第一行为一个整数N和w,分别表示宝物种数和采集车的最大载重。

接下来n行每行三个整数,其中第i行第一个数表示第i类品价值,第二个整数表示一件该类物品的重量,第三个整数为该类物品数量。

输出格式:

输出仅一个整数ans,表示在采集车不超载的情况下收集的宝物的最大价值。

输入输出样例

输入样例#1:

1
2
3
4
5
4 20
3 9 3
5 9 1
9 4 2
8 1 3

输出样例#1:

1
47

说明

对于30%的数据:$n≤∑m_i≤10^4$;$0≤W≤10^3$。

对于100%的数据:$n≤∑m_i≤10^5$;$0 <w≤4*10^4$;$1≤n<100$。

题解

完全背包裸题,二进制优化见P2851 [USACO06DEC]最少的硬币The Fewest Coins[dp]

这里用的单调队列优化,毕竟跑得快一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=100+10;
const int maxm=5e4+1000;
int n,W;
int v[maxn],w[maxn],s[maxn];
int dp[maxm];
int q[maxm],l,r,a,b;
int d[maxm];
int main()
{
n=read();W=read();
//W+=100;
dp[0]=0;
for (int i=1;i<=n;i++) v[i]=read(),w[i]=read(),s[i]=read();
for (int i=1;i<=n;i++)
{
b=w[i]-1;
for (int j=0;j<=b;j++)
{
l=1;r=0;
a=(W-j)/w[i];
for (int k=0;k<=a;k++)
{
while (l<=r&&q[r]<(dp[j+k*w[i]]-k*v[i])) r--;
while (l<=r&&k-d[l]>s[i]) l++;
r++;q[r]=dp[j+k*w[i]]-k*v[i];d[r]=k;
dp[j+k*w[i]]=q[l]+k*v[i];
}
}
}
cout<<dp[W];
return 0;
}