[THUPC 2023 初赛] 背包
题目描述
本题中，你需要解决完全背包问题。
有
n
n
n
种物品，第
i
i
i
种物品单个体积为
v
i
v_i
v
i
、价值为
c
i
c_i
c
i
。
q
q
q
次询问，每次给出背包的容积
V
V
V
，你需要选择若干个物品，每种物品可以选择任意多个（也可以不选），在选出物品的体积的和
恰好
为
V
V
V
的前提下最大化选出物品的价值的和。你需要给出这个最大的价值和，或报告不存在体积和恰好为
V
V
V
的方案。
为了体现你解决 NP-Hard 问题的能力，
V
V
V
会远大于
v
i
v_i
v
i
，详见数据范围部分。
输入格式
第一行两个整数
n
,
q
n,q
n
,
q
，表示物品种数和询问次数。
接下来
n
n
n
行每行两个整数
v
i
,
c
i
v_i,c_i
v
i
,
c
i
描述一种物品。
接下来
q
q
q
行每行一个整数
V
V
V
描述一次询问中背包的体积。
输出格式
对于每组询问输出一行一个整数。若不存在体积和恰好为
V
V
V
的方案，输出
-1
；否则输出最大的选出物品的价值和。
样例 #1
样例输入 #1
2 2
6 10
8 15
100000000001
100000000002
样例输出 #1
-1
187500000000
提示
样例解释 1
第二组询问的最优方案为：选择
3
3
3
个物品
1
1
1
和
12499999998
12499999998
12499999998
个物品
2
2
2
。
子任务
对于所有测试数据，
1
≤
n
≤
50
,
1
≤
v
i
≤
1
0
5
,
1
≤
c
i
≤
1
0
6
,
1
≤
q
≤
1
0
5
,
1
0
11
≤
V
≤
1
0
12
1 \le n \le 50, 1 \le v_i \le 10^5, 1 \le c_i \le 10^6, 1 \le q \le 10^5, 10^{11} \le V \le 10^{12}
1
≤
n
≤
50
,
1
≤
v
i
≤
1
0
5
,
1
≤
c
i
≤
1
0
6
,
1
≤
q
≤
1
0
5
,
1
0
11
≤
V
≤
1
0
12
。
题目来源
来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。
题解等资源可在
https://github.com/THUSAAC/THUPC2023-Pre
查看。
(from luogu)
考虑
c
p
/
v
p
c_p/v_p
c
p
/
v
p
最大的item
(
v
p
,
c
p
)
(v_p,c_p)
(
v
p
,
c
p
)
，最后的答案一定是尽量多取
当
i
i
i
足够大时，
f
i
+
v
p
=
f
i
+
c
p
f_{i+v_p}=f_i+c_p
f
i
+
v
p
=
f
i
+
c
p
考虑同余最短路，模
v
p
v_p
v
p
发现无法定义图中边的边权，最后会陷入无限负环，无法最短路。
令
f
i
=
g
i
m
o
d
m
+
⌊
i
v
p
⌋
∗
c
p
f_i=g_{i \mod m} + \lfloor \frac {i} {v_p} \rfloor *c_p
f
i
=
g
i
mod
m
+
⌊
v
p
i
⌋
∗
c
p
对于
g
i
g_i
g
i
求最短路
对于
f
i
f_i
f
i
取物品
(
v
x
,
c
x
)
(v_x,c_x)
(
v
x
,
c
x
)
并转移到
f
j
f_j
f
j
等价于
f
i
+
c
x
=
g
i
m
o
d
m
+
⌊
i
v
p
⌋
∗
c
p
+
c
x
f_{i+c_x}=g_{i \mod m} + \lfloor \frac {i} {v_p} \rfloor *c_p+c_x
f
i
+
c
x
=
g
i
mod
m
+
⌊
v
p
i
⌋
∗
c
p
+
c
x
=
g
i
m
o
d
m
+
c
x
+
(
⌊
i
v
p
⌋
−
⌊
i
+
v
x
v
p
⌋
)
c
p
+
⌊
i
+
v
x
v
p
⌋
∗
c
p
=g_{i \mod m} +c_x + (\lfloor \frac {i} {v_p} \rfloor -\lfloor \frac {i+v_x} {v_p} \rfloor )c_p+ \lfloor \frac {i+v_x} {v_p} \rfloor *c_p
=
g
i
mod
m
+
c
x
+
(⌊
v
p
i
⌋
−
⌊
v
p
i
+
v
x
⌋)
c
p
+
⌊
v
p
i
+
v
x
⌋
∗
c
p
转移到
g
j
m
o
d
m
+
⌊
j
v
p
⌋
∗
c
p
g_{j \mod m} + \lfloor \frac {j} {v_p} \rfloor *c_p
g
j
mod
m
+
⌊
v
p
j
⌋
∗
c
p
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define MAXN (60+10)
ll v[MAXN],c[MAXN];
ll f[500000+10];
int main()
{
// freopen("D.in","r",stdin);
// freopen(".out","w",stdout);
int n=read(),q=read(),p=1;
For(i,n) {
cin>>v[i]>>c[i];
if(v[i]*c[p]<v[p]*c[i]) {
p=i;
}
}
const ll M=v[p],w=c[p];
Rep(i,M) f[i]=-1e18;f[0]=0;
For(i,n) {
int ma=__gcd(v[i],M);
Rep(j,ma) {
for(int t=j,_=0;_<2;_+=t==j){
int q=(t+v[i])%M;
if(f[t]!=-1e18)
gmax(f[q],f[t]+c[i]-(t+v[i])/M *w)
t=q;
}
}
}
For(i,q) {
ll qv;
cin>>qv; ll p=qv%M;
if(f[p]==-1e18)puts("-1");
else {
cout<<f[p]+qv/M*w<<endl;
}
}
return 0;
}