隐藏
「HEOI2013」Eden的新背包问题 - CDQ分治左右逼近+多重背包 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「HEOI2013」Eden的新背包问题 - CDQ分治左右逼近+多重背包

题目大意

    每个物品有三个属性:价值,价格,个数。多次询问缺一个物品在一定总钱数限制内 选择物品 可以得到的最大价值和。


题目分析

本题和消失之物很类似。
我们可以使用CDQ分治左右逼近的方法解决本题。

通过左右逼近更新背包来做到缺一个物品的条件。
多重背包可以使用单调队列优化(待补坑学习笔记),也可以使用二进制拆分。
不知道为什么比二进制拆分跑得慢,可能是因为常数原因(人傻常数大)。
时间复杂度:

其中$V$表示总钱数范围。
根据主定理可得(在多项式意义下将$V$视作常数):


代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define pii pair<int,int>
#define mp make_pair

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=1005,maxq=300005,maxm=1005;

struct Thing {
int cost,value,num;
} a[maxn];

struct Query {
int x,val,id;
bool operator < (const Query& b) const {
return x<b.x;
}
} Q[maxq];

int n,q,f[maxm],ans[maxq],pos=1;

void trans(const Thing& a) {
for(int mod=0; mod<a.cost; mod++) {
deque<pii>Q;
for(int i=0,index; (index=i*a.cost+mod)<=1000; i++) {
while(!Q.empty()&&Q.front().first<i-a.num)Q.pop_front();
while(!Q.empty()&&Q.back().second<=f[index]-i*a.value)Q.pop_back(); //允许自己转移到自己
Q.push_back(mp(i,f[index]-i*a.value));
f[index]=Q.front().second+i*a.value;
}
}
}

void CDQBinary(int Left,int Right) {
if(Left==Right) {
while(pos<=q&&Q[pos].x==Left) {
ans[Q[pos].id]=f[Q[pos].val];
pos++;
}
return;
}
int mid=(Left+Right)>>1,tmp[1005];
memcpy(tmp,f,sizeof(f));
for(int i=mid+1; i<=Right; i++)trans(a[i]);
CDQBinary(Left,mid);
memcpy(f,tmp,sizeof(tmp));
for(int i=Left; i<=mid; i++)trans(a[i]);
CDQBinary(mid+1,Right);
}

int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i].cost=Get_Int();
a[i].value=Get_Int();
a[i].num=Get_Int();
}
q=Get_Int();
for(int i=1; i<=q; i++) {
Q[i].x=Get_Int()+1;
Q[i].val=Get_Int();
Q[i].id=i;
}
sort(Q+1,Q+q+1);
CDQBinary(1,n);
for(int i=1; i<=q; i++)printf("%d\n",ans[i]);
return 0;
}
姥爷们赏瓶冰阔落吧~