自动搬运

查看原文

来自洛谷，原作者为

	是青白呀 咕咕咕？咕咕咕！

搬运于2025-08-24 22:59:02，当前版本为作者最后更新于2024-05-29 22:29:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先有一个比较显然的 dp：设 $dp_i$ 表示第 $i$ 个人操作结束后的最大伤害总量，转移为 $dp_i=dp_j+d_{b_i}+val_{j+1,i}$，其中 $val_{x,y}$ 表示在 $x$ 处触发异常状态，在 $y$ 处发动攻击，中间的其他位置都不操作的额外伤害。

一个显然的发现是，对于所有 $val_{j+1,i}=0$ 的转移点 $j$，$j=i-1$ 的情况是最优的。因而对于其它情况，我们只需要考虑和 $b_i$ 能触发暴击的 $a_j$ 即可。

由于暴击规则只有 $m$ 条，考虑根号分治。对于有超过 $\sqrt m$ 条暴击规则的 $b_i$，我们维护一个 $maxa_{b_i}$ 表示能转移到攻击模式 $b_i$ 的最大 $dp_j+c_{a_{j+1},b_i}$ 的值，其中 $c_{x,y}$ 表示异常状态 $x$ 和攻击模式 $y$ 对应的暴击的额外伤害，每次可以直接转移；对于不超过 $\sqrt m$ 条暴击规则的 $b_i$，我们维护一个 $maxs_{x}$ 表示到目前为止，异常状态 $x$ 对应的最大的 $dp$ 值，每次枚举和 $b_i$ 有关的所有暴击规则来转移。

更新完 $dp_i$ 的值之后，我们假设在 $i$ 处触发异常状态，用 $dp_{i-1}$ 更新 $maxs_{a_i}$，并枚举所有规则数大于 $\sqrt m$ 的 $b_x$，用 $dp_{i-1}+c_{a_i,b_x}$ 更新 $maxa_{b_x}$ 的值即可。

总时间复杂度 $O(n\sqrt m)$。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) x*2
#define rs(x) x*2+1
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long
#define qingbai 666
using namespace std;
typedef long long ll;
const int N=2e5+5,S=(1<<20)+5,mo=1e9+7,inf=(ll)1e18+7;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int n,m,x,y;
int d[N],a[N],b[N];
struct rule{
	int x,y,c;
}r[N];
int dp[N],cnt[N],upp;
vector<pii>atk[N],sit[N];
int maxs[N],maxa[N];
signed main(){
	read(n),read(m),read(x),read(y),upp=sqrt(m);
	rep(i,1,x)
	    read(d[i]);
	rep(i,1,n)
	    read(a[i]),read(b[i]);
	rep(i,1,m){
		read(r[i].x),read(r[i].y),read(r[i].c);
		cnt[r[i].y]++;
	}
	rep(i,1,m){
		if(cnt[r[i].y]>upp)sit[r[i].x].push_back(mp(r[i].y,r[i].c));
		else atk[r[i].y].push_back(mp(r[i].x,r[i].c));
	}
	rep(i,1,x)
	    maxa[i]=-inf;
	rep(i,1,y)
	    maxs[i]=-inf;
	rep(i,1,n){
		dp[i]=dp[i-1]+d[b[i]];
		if(cnt[b[i]]>upp)dp[i]=max(dp[i],maxa[b[i]]+d[b[i]]);
		else{
			for(auto j:atk[b[i]])
				dp[i]=max(dp[i],maxs[j.fir]+j.sec+d[b[i]]);
		}
		maxs[a[i]]=max(maxs[a[i]],dp[i-1]);
		for(auto j:sit[a[i]])
		    maxa[j.fir]=max(maxa[j.fir],dp[i-1]+j.sec);
	}
	printf("%lld\n",dp[n]);
	return 0;
}