成都集训-test0717

Diavolo / 2023-07-17 / 原文

今天的模拟赛太逆天了。 $\text{NOIP}$ 模拟赛一紫三黑。

得分： $100+14+0+14=128$ ,被吊打。

T1 珠宝

题目描述

有 $n$ 个物品，每一个物品有一个空间 $w_i$ 和一个价值 $v_i$ 。

你有一个空间为 $i$ 的背包，问最多可以装下多少价值的物品。

问价值 $i \leqslant K$ 时的每一个答案。

数据范围 ： $n \leqslant 1e6$ , $K \leqslant 5e4 $ , $w \leqslant 300$ 。

思路点拨

我们按照一般的 $\text{01}$ 背包的思路，本题可以做到 $O(nk)$ ，严重超时。

我们比较一般的背包问题的数据规模和本题的数据规模，本题的物品数量十分庞大，但是物品的空间很小。

我们从物品的空间下手，从 $1$ 到 $300$ 枚举一个空间 $V$ 。对于每一个空间时 $V$ 的物品打包考虑。

首先，我们可以将这些物品价值降序排序，因为我们在同样的空间下总是会先选价值大的。

接下来，我们对这些物品做前缀和，保存到数组 $g_{i \times V}$ 中，表示选择 $i$ 个空间为 $V$ 的物品的价值。

转移的时候，我们发现，两个状态 $f_{i}$ 和 $f_{j}$ 会互相影响仅当 $i \mod V = j \mod V$ 。

所以我们枚举我们要转移的状态 $\mod V$ 的余数，假设他为 $z$ 。

那么我们将形如 $f_{i \times V+z}$ 的状态放在一起考虑，得到转移方程：

\[f_{i \times V+z} = \max \{ f_{i \times V+z} , \max \{ f_{j\times V+z} + g_{(j-i)\times V}\} \} \]

这个式子对我们的时间没有任何的优化，但是 $g$ 函数的增长率时单调不递增的。证明略。

所以我们的决策点有单调性，使用分治或者单调队列上二分均可通过。本题还算是比较可做的。

$code$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+10;
const int N=5e4+10,MV=3e2+10;
const int MAXV=300;
int n,k;
struct node{
	int w,v;
}a[MAXN];
int f[MAXN];
vector<int> e[MV];//存储每一个权值的物品 
bool cmp(int A,int B){
	return A>B;
}
int w[N],temp[N],tot;//转移权值
int g[N];
void cdq(int l,int r,int L,int R){
	if(l>r) return ;
	int mid=(l+r)/2;
	int mx=-1,pos=0;
	for(int i=L;i<=min(R,mid);i++)
		if(temp[i]+w[mid-i]>mx){
			mx=temp[i]+w[mid-i];
			pos=i;
		}
	g[mid]=mx;
	cdq(l,mid-1,L,pos);
	cdq(mid+1,r,pos,R);
}
signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i].w,&a[i].v);
	for(int i=1;i<=n;i++)
		e[a[i].w].push_back(a[i].v);
	for(int i=1;i<=MAXV;i++)
		sort(e[i].begin(),e[i].end(),cmp);
	for(int i=1;i<=MAXV;i++){
		if(!e[i].size()) continue;
		for(int j=1;j*i<=k;j++){
			if(j<=e[i].size())
				w[j]=w[j-1]+e[i][j-1];
			else w[j]=w[j-1];
		}
		for(int mod=0;mod<i;mod++){ 
			tot=0;
			for(int j=0;j*i+mod<=k;j++)
				temp[++tot]=f[j*i+mod];
			cdq(1,tot,1,tot);
			for(int j=0;j*i+mod<=k;j++)
				f[j*i+mod]=max(f[j*i+mod],g[j+1]);
		}
	}
	int mx=0;
	for(int i=1;i<=k;i++){
		mx=max(mx,f[i]);
		printf("%lld ",mx);
	}
	return 0;
}