题解--探险者笔记III
abruce
·
·
题解
关于探险者笔记和探险者笔记II，第一个出 R1 的时候被拒了，第二个重了，总之就是SPFA了。
20pts
题目给的信息非常难看，我们需要将其简化。我们设 c_i=\sum\limits_{k=1}^{sum_i}b_{a_{i_k}}，这很明显是个定值。然后我们再把第 i 个成就需要的关卡用一个二进制数表示出来，设其为 p_i。我们便可以推出一个 O(m^2) 的 dp：
直接暴力转移即可。
### 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)$，可以通过本题。
```cpp
#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;
}
```