Codeforces Round 980 (Div. 2) D

D_Skipping

妙啊，题出的真的好，虽然没写出来

---

我们最后一定会经过 $1 \dots k$ 这些点，但这些点中有些点可能是跳过的，所以边遍历边用$1 \dots k$ 的 $a[i]$ 和减去到达 $i$ 位置的最小值 $dp[i]$ 就能得到最远到达 $k$ 位置的最大值，接着枚举 $k$ 取每个位置的最大的最大即可。

我们设 $dp[i]$ 为到达 $i$ 点的小花费（也就是我们跳过的点的分数的和的最小），对于位置 $i$ ，只有小于 $i$ 的并且 $b[i]$ 大于 等于 $i$ 的点才能对 $dp[i]$ 造成直接影响。设该点的坐标是 $p$ , 那么$p \in \{ p < i , b[p]>=i \}$。

因此我们可以维护一个小根堆堆来使得我们每次的花费最小，设该堆为 $heap$ ，如果heap.top().b < i，那么堆顶弹出，直到heap.top().b >= i，这符合我们之前的第2个条件，又因为我们是边循环边入堆，因此我们的堆中的位置都一定小于 $i$ 。在入堆时要记得加上到达这个位置的最小值。

 

void solve(){
    ans = -INF ;
    cin >> n ;
    _rep(i,1,n){
        cin >> a[i] ;
        dp[i] = INF ;
    }
    _rep(i,1,n){
        cin >> b[i] ;
    }
    priority_queue<PII> heap ;
    heap.push({-a[1],b[1]}) ;
    dp[1] = 0 ;
    _rep(i, 2, n){
        while(heap.size() && heap.top().second < i) heap.pop() ; 
        if(heap.size() == 0) break ;
        dp[i] = -heap.top().first ; 
        if(b[i] > i ) heap.push({-(a[i] + dp[i]),b[i]}) ;
    }

    int sum = 0 ;
    _rep(i,1,n){
        sum += a[i] ;
        ans = max(ans,sum - dp[i]) ;
    }
    cout << ans << endl ;

}