题解：P10381 「HOI R1」杂赛选比

int_R · 2024-04-29 08:28:56 · 题解

转化成在 i 处解锁一次相当于花费了 a_i 的代价，枚举解锁到的最远位置，当前点答案为前缀和减去最小代价。

最小代价转换成最短路，对于每个 i\in[1,n]，连一条由 i 到 \min(i+a_i,n) 边权为 a_i 的边。对于每个 i\in[2,n]，连一条由 i 到 i-1 边权为 0 的边。跑最短路即可得到最小代价。

感觉比线段树好多了啊！

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<queue>
#define int long long
using namespace std;
const int MAXN=1e5+10,MAXM=2e5+10,INF=1e15;
int T,n,a[MAXN],s[MAXN],dis[MAXN],ans;
int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],cnt;
typedef pair<int,int> P;bool vis[MAXN];
inline void add(int x,int y,int v)
{
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt,val[cnt]=v;return ;
}
inline void dij()
{
    priority_queue < P,vector<P>,greater<P> > q;
    q.push({dis[1]=0,1});
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x]) continue;vis[x]=true;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];if(dis[y]<=dis[x]+val[i]) continue;
            q.push({dis[y]=dis[x]+val[i],y});
        }
    }
}
inline void work()
{
    cin>>n,cnt=ans=0;
    for(int i=1;i<=n;++i) head[i]=vis[i]=0,dis[i]=INF;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i],s[i]=s[i-1]+a[i];
        if(i>1) add(i,i-1,0);add(i,min(i+a[i],n),a[i]);
    }
    dij();for(int i=1;i<=n;++i) ans=max(ans,s[i]-dis[i]);
    cout<<ans<<'\n';return ;
}
signed main()
{
#ifdef ONLINE_JUDGE
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#else
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>T;while(T--) work();
    return 0;
}