P17583 [JAG 2026 Summer Camp #3] Treasure Hunting题解

zpy12345 · 2026-10-21 14:00:20 · 题解

安利一下我的博客！

思路

对于每个宝箱 (x_i,y_i) 我们抵达他的时间一定是 x_i+y_i，在此时间之前，假设我们已经确定向上走了 a_i 步，向右走了 b_i 步，我们将 (x_i,y_i) 的坐标修改为 (x_i-a_i,y_i-b_i)，表示我们还需要额外走的步数。

这样转移就简单了，设 dp_i 表示抵达 i 宝箱时可以获得的最大金币数，可以从满足 x_j\le i 且 y_j\le i 的宝箱 j 转移。先按横坐标排序然后用树状数组维护一下纵坐标即可。

代码

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int m,n,s[N],ss[N];
struct js
{
    int x,y,z;
}a[N];
int lowbit(int x){
    return x&(-x);
}
bool cmp(js x,js y)
{
    if(x.x==y.x) return x.y<y.y;
    return x.x<y.x;
 } 
long long tree[N];
void update(int x,long long y)
{
    for(int i=x;i<=m+1;i+=lowbit(i)) tree[i]=max(tree[i],y);
}
long long query(int x)
{
    long long res=0;
    for(int i=x;i;i-=lowbit(i)) res=max(res,tree[i]);
    return res;
}
long long dp[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        s[i]=s[i-1],ss[i]=ss[i-1];
        char c;
        cin>>c;
        if(c=='R') s[i]++;
        else if(c=='U') ss[i]++;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
        int u=a[i].x+a[i].y;
        a[i].x-=s[u],a[i].y-=ss[u];
    }
    sort(a+1,a+1+n,cmp);
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].x<0||a[i].y<0) continue ;
        dp[i]=query(a[i].y+1)+a[i].z;
        ans=max(ans,dp[i]);
        update(a[i].y+1,dp[i]);
    }
    cout<<ans;
    return 0;   
}