My Blogs
P10542 [THUPC2024] RPG
一个有配合的“状态加攻击”一定是一个连续段，段内都在摸鱼。所以设 $f_i$ 表示考虑了前 $i$ 个人的最大收益：
\[f_i=\begin{cases} f_{i-1}+d_{b_i}\\ \max_{(x,y,z)\in \mathbb{E},y=b_i}g_x+z+d_{b_i} \end{cases}\]其中 $g_i$ 表示满足 $a_j=i$ 的最大的 $f_{j-1}$。暴力做是 $n^2$ 的，原因在于一个 $y$ 对应的 $x$ 可能会过多。
然后第二个式子只和 $y$ 有关。所以考虑根号分治，对于一种 $y$，如果其入度过多，将其单独处理（每转移一位统计存在 $x=a_i$ 的 $y$）。取阈值为 $\sqrt n$ 可以做到 $\mathcal O(n\sqrt n)$。实现不能太烂（有点卡常）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int n,m,X,Y,d[200010],a[200010],b[200010];
int val[200010],now[200010],f[200010];
vector<pii> ve[200010];
vector<pii> nex[200010];
vi tmp;
const int B=700;
inline void mian()
{
read(n,m,X,Y);int x,y,z;
for(int i=1;i<=X;++i)read(d[i]);
for(int i=1;i<=n;++i)read(a[i],b[i]);
while(m--)read(x,y,z),ve[y].eb(mp(x,z));
memset(val,128,sizeof(val)),memset(now,128,sizeof(now));
for(int i=1;i<=X;++i)if(ve[i].size()>B)
for(auto p:ve[i])nex[p.fi].eb(mp(i,p.se));
for(int i=1;i<=n;++i)
{
f[i]=f[i-1]+d[b[i]];
if(ve[b[i]].size()<=B)
{
for(auto p:ve[b[i]])
Mmax(f[i],val[p.fi]+p.se+d[b[i]]);
}
else Mmax(f[i],now[b[i]]+d[b[i]]);
Mmax(val[a[i]],f[i-1]);
for(auto p:nex[a[i]])Mmax(now[p.fi],p.se+f[i-1]);
}
write(f[n]);
}