Codeforces Round 980 (Div. 2) D 题解

Problem - D - Codeforces--Skipping

思路:看了RegenFallen大佬的写法，很美妙..

首先可以发现,到达某个点之后,可以一直选择提交题目,直至题目1.
key:因为选择了跳题就会丢失分数score[i],即通过花费score[i]跳到另一个点!!
定义dp[i]为花费最小的代价到达点i.那么答案就是pre[i]-dp[i].
如果1-->4花费0的话,即1-->2,1-->3也是花费为0.
如果暴力更新的话是不行的,那么这一部分就需要优先队列来优化.
往回跳的话肯定是更差的,不考虑.

int n;
int score[400005],to[400005];
int dp[400005]; //定义dp[i]为花费最小的代价到达点i.
//思路:首先可以发现,到达某个点之后,可以一直选择提交题目,直至题目1.
//key:因为选择了跳题就会丢失分数score[i],即通过花费score[i]跳到另一个点!!
//定义dp[i]为花费最小的代价到达点i.那么答案就是pre[i]-dp[i].
//如果1-->4花费0的话,即1-->2,1-->3也是花费为0.
//如果暴力更新的话是不行的,那么这一部分就需要优先队列来优化.
//往回跳的话肯定是更差的,不考虑.
//https://codeforces.com/contest/2024/problem/D
void solve(){   //D--优先队列优化dp--太妙了
    cin>>n;
    for(int i=1;i<=n;i++) dp[i]=LONG_LONG_MAX/2;  //init
    for(int i=1;i<=n;i++) cin>>score[i];
    for(int i=1;i<=n;i++) cin>>to[i];
    priority_queue<pair<int,int>> pq; //用作小根堆. <代价,前y个点可用>
    dp[1]=0;
    pq.emplace(-score[1],to[1]);
    for(int i=2;i<=n;i++){
        while(pq.size()&&pq.top().second<i) pq.pop();
        if(pq.empty()) break; //即当前点即后面点都是不可达的.
        dp[i]=-pq.top().first;
        if(to[i]>i) pq.emplace(-(dp[i]+score[i]),to[i]);
    }
    int ans=0,sum=0;
    for(int i=1;i<=n;i++){
        sum+=score[i];
        ans=max(ans,sum-dp[i]);
    }
    cout<<ans<<endl;
}