自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:33:35，当前版本为作者最后更新于2021-04-05 16:49:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关于探险者笔记和探险者笔记II，第一个出 R1 的时候被拒了，第二个重了，总之就是SPFA了。

20pts

题目给的信息非常难看，我们需要将其简化。我们设 $c_i=\sum\limits_{k=1}^{sum_i}b_{a_{i_k}}$，这很明显是个定值。然后我们再把第 $i$ 个成就需要的关卡用一个二进制数表示出来，设其为 $p_i$。我们便可以推出一个 $O(m^2)$ 的 dp：
$f_i=\max\limits_{j=1}^{i-1} f_j+v_i(c_j+w\ge c_i,p_j\in p_i)$。
直接暴力转移即可。

50~60pts

上面那个式子本质上是个三维偏序，考虑用 cdq 分治加速这个转移。
只需用 cdq 解决 $c_j+w\ge c_i$，然后暴力枚举子集转移 $p_j\in p_i$ 即可。
时间复杂度 $O(2^nm\log m)$。

100pts

暴力枚举子集时间复杂度显然不对，我们考虑怎么优化枚举。这时就有两种方法：
一种是修改时把 $p_j$ 存下来，查询时枚举 $p_i$ 的子集，这样修改 $O(1)$，查询 $O(2^n)$。
另一种是修改时枚举所有 $p_j$ 的超集进行预处理，查询时直接在数组中查询，这样修改 $O(2^n)$，查询 $O(1)$。
我们考虑如何平衡这个复杂度。我们可以把一个 $18$ 位的二进制数劈成前 $9$ 位和后 $9$ 位。然后定义一个二维数组 $g_{s,t}$ 表示 $p_i$ 前 $9$ 位为 $s$,$p_j$ 后 $9$ 位为 $t$ 时的最优决策。
在修改时，我们枚举 $p_j$ 前 $9$ 位的超集，然后把它的后 $9$ 位不枚举，直接存起来。
在查询时，我们就直接调用 $p_i$ 的前 $9$ 位，再枚举其后 $9$ 位即可。
这样就达到了平衡复杂度的目标，总时间复杂度 $O(2^{\frac{n}{2}}m\log m)$，可以通过本题。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,maxm=512;
struct node {
	int a,b,v,id;
	friend bool operator<(node a,node b) {
		return a.a==b.a?a.id<b.id:a.a>b.a;
	}
} p[maxn],zc[maxn];
int g[maxm][maxm],n,f[maxn],b[maxn],m,w;
void add(int x,int v) {//修改
	int gw=x>>9,dw=x&511;
	if(n<=9) {
		g[0][dw]=max(g[0][dw],v);//如果只有8位，修改就不用枚举，减小常数。
		return;
	}
	for(register int i=gw;; i=(i+1)|gw) {//枚举前8位的超集
		g[i][dw]=max(g[i][dw],v);//后8位直接储存
		if(i==511)break;
	}
}
void clr(int x) {//清空，道理同修改
	int gw=x>>9,dw=x&511;
	if(n<=9) {
		g[0][dw]=0;
		return;
	}
	for(register int i=gw;; i=(i+1)|gw) {
		g[i][dw]=0;
		if(i==511)break;
	}
}
int ask(int x) {
	int gw=x>>9,dw=x&511,sum=0;
	for(register int i=dw;; i=(i-1)&dw) {//查询时枚举后8位
		sum=max(sum,g[gw][i]);
		if(!i)break;
	}
	return sum;
}
void cdq(int l,int r) {
	if(l==r)return;
	int mid=(l+r)/2,lst=l;
	cdq(l,mid);
	sort(p+l,p+mid+1),sort(p+mid+1,p+r+1);
	for(register int i=mid+1; i<=r; i++) {
		while(p[lst].a>=p[i].a-w&&lst<=mid) {
			add(p[lst].b,f[p[lst].id]);
			lst++;
		}
		f[p[i].id]=max(f[p[i].id],ask(p[i].b)+p[i].v);
	}
	for(register int i=l; i<lst; i++)clr(p[i].b);
	for(register int i=l; i<=r; i++)zc[p[i].id]=p[i];
	for(register int i=l; i<=r; i++)p[i]=zc[i];
	cdq(mid+1,r);
}//注意cdq优化dp必须按中序遍历
int main() {
	int siz,x;
	scanf("%d%d%d",&n,&m,&w);
	for(register int i=1; i<=n; i++)scanf("%d",&b[i]);
	for(register int i=1; i<=m; i++) {
		scanf("%d%d",&p[i].v,&siz);
		for(register int j=1; j<=siz; j++) {
			scanf("%d",&x);
			p[i].a+=b[x],p[i].b|=1<<x-1;
		}
		p[i].id=i,f[i]=p[i].v;
	}
	cdq(1,m);
	int ans=0;
	for(register int i=1; i<=m; i++)ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}