题解：P10542 [THUPC2024] RPG

· · 题解

首先有一个比较显然的 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;
}