loj6039. 「雅礼集训 2017 Day5」珠宝

题目大意

有 \(n\) 个物品，第 \(i\) 个费用为 \(w_i\) ，价值为 \(v_i\) ，对于 \(k\in[1,m]\) 求费用为 \(m\) 时能获得的最大价值。

\(1\leq n\leq 10^6,1\leq m\leq 5\times 10^4,1\leq w_i\leq 300,1\leq v_i\leq 10^9\)

思路

\(n\) 很大，但 \(w_i\) 很小，于是我们考虑以其为突破口。

我们可以把 \(w_i\) 相同的按照 \(v_i\) 从大到小排序，设这里有 \(x_i\) 个相同的 \(w_i\) ，那么对于每个 \(w_i\) ，我们就可以选择 \(0 \sim x_i\) 个。

设 \(f_{i,j}\) 表示 \(w=i\) 时费用为 \(j\) 的最大价值和，那么有

\(f_{i,j}=f_{i-1,j-ki}+s_{i,z}\)

（ \(s_{i,z}\) ​表示 \(w=i\) 的物品中前 \(z\) 大的价值和）

这个式子明显是一个01背包的状态转移方程，很难用常规的优化，但是可以用四边形不等式。至于证明，我们有 \(w_{i,j}=s_{j-i}\)

要证明：
\(w_{i,j}+w_{i+1,j+1}\geq w_{i,j+1}+w_{i+1,j}\)
\(s_{j-i}+s_{j-i}\geq s_{j-i+1}+s_{j-i-1}\)
上面两个式子是等价的

因为 \(s_{i+1} - s_{i}\) 是递减的，所以成立。

那么我们现在对于每个枚举的 \(w=i\) ，

先把所有的 $ i*k + j(\ j\in[0,i)\ )$ 都分成一组。

对于每一组我们都可以用四边形不等式优化：

对于所有决策用一个单调队列记录，并且记录 \(z_i\) 表示队列里第 \(i\) 个决策和第 \(i+1\) 个决策的交叉点（在 \(z_i\) 之前 \(q_{i}\) 更优， \(z_i\) 以之后 \(q_{i+1}\) 更优）。

每次弹出队列前面的来找答案，加入的时候我们就二分出队尾和新加入的决策交叉点，然后一直弹尾部直到不交叉。

时间复杂度： \(O(m w \log m)\)

#include<bits/stdc++.h>
#define ll long long
#define N 50010
using namespace std;
ll n,m,g,f[2][N],q[N],z[N];
vector<ll>w[310];
bool cmp(ll x,ll y){
	return x>y;
}
ll calc(ll i,ll j,ll p,ll k){
	return f[!g][i*p+k]+w[p][j-i-1];
}
ll bound(ll i,ll j,ll p,ll k){
	ll l = i+1,r = (m-k)/p;
	while(l<=r){
		ll mid = (l+r)>>1;
		if(calc(i,mid,p,k)<calc(j,mid,p,k))
			l = mid+1;
		else r = mid-1;
	}
	return l;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i = 1;i<=n;i++){
		ll c,v;
		scanf("%lld%lld",&c,&v);
		w[c].push_back(v);
	}
	g = 0;
	for(ll p = 1;p<=300;p++){
		if(w[p].empty()) continue;
		g^=1;
		memcpy(f[g],f[!g],sizeof(f[g]));
		sort(w[p].begin(),w[p].end(),cmp);
		while(w[p].size()<=m/p) w[p].push_back(0);
		for(ll i = 1;i<w[p].size();i++) w[p][i]+=w[p][i-1];
		for(ll k = 0;k<p;k++){
			ll head = 1,tail = 0;
			for(ll i = 0;i*p+k<=m;i++){
				while(head<tail&&z[head]<=i) head++;
				if(head<=tail) f[g][i*p+k] = max(f[g][i*p+k],calc(q[head],i,p,k));
				while(head<tail&&z[tail-1]>=bound(i,q[tail],p,k)) tail--;
				z[tail] = bound(i,q[tail],p,k);
				q[++tail] = i;
			}
		}
	}
	for(ll i = 1;i<=m;i++)
		printf("%lld ",f[g][i]);
	return 0;
}

_{为此我还专门学了四边形不等式优化}