CF2023B/CF2024D#

题意分析#

首先我们可以发现，在第 $i$ 个点上时，所得的得分为从 $1$ 到 $i$ 之和减去跳过的问题。所以此题可以转化为求跳过的题目的最小值。所以答案就是

$ans=\max_{i=1}^{n}(sum_i-dis_i)$

其中的 $sum_i$ 表示从 $1$ 到 $i$ 的前缀和， $dis_i$ 表示从 $1$ 到 $i$ 的代价最小值。

关于如何求 $dis_i$ ，我们可以建图跑最短路，对 $i\rightarrow i-1$ 建边，权值为 $0$ ，对 $i\rightarrow b_i$ 建边，权值为 $a_i$ 。之后通过最短路求出 $dis_i$ ，然后枚举答案即可。

Code#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 4e5+100;
10
const int INF = 1e15;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
// int dis[MaxN];
14
vector<pair<int,int>>G1[MaxN];
15
struct Dijkstra{
16
  int d[MaxN], vis[MaxN];
17
  struct Point {
18
    int id, x;
19
    inline bool operator<(const Point &aa)const {
20
      return x > aa.x;
21
    }
22
  };
23
  priority_queue<Point>q;
24
  inline void solve(int S) {
25
    for(int i = 1; i <= N; i++) d[i] = INF, vis[i] = 0;
26

27
    d[S] = 0;
28
    q.push((Point){ S, 0 });
29
    while(!q.empty()) {
30
      auto [x, w] = q.top(); q.pop();
31
      if (vis[x]) continue;
32
      vis[x] = 1;
33
      for(auto it : G1[x]) {
34
        int y = it.first;
35
        int z = it.second;
36
        if(d[x] + z < d[y]) {
37
          d[y] = d[x] + z;
38
          if(!vis[y])  q.push((Point){ y, d[y] });
39
        }
40
      }
41
    }
42
  }
43
};
44
inline void Solve()
45
{
46
  cin>>N;
47
    // vector<pair<int,int>> G1[MaxN];
48
    vector<int>sum(N+1);
49
    vector<int>a(N+1);
50
    for(int i=1;i<=N;i++){
51
        cin>>a[i];
52
        sum[i]=sum[i-1]+a[i];
53
        if(i!=1)
54
            G1[i+1].push_back(make_pair(i,0));
55
    }
56
    for(int i=1;i<=N;i++){
57
        int x;
58
        cin>>x;
59
        G1[i].push_back(make_pair(x,a[i]));
60
    }
61
    Dijkstra dij;
62
    dij.solve(1);
63
    int ans=0;
64
    for(int i=1;i<=N;i++){
65
        // cout<<dij.d[i]<<" ";
66
        ans=max(ans,sum[i]-dij.d[i]);
67
        G1[i].resize(0);
68
    }
69
    cout<<ans<<endl;
70
}
71
signed main()
72
{
73
#ifndef ONLINE_JUDGE
74
    freopen(".in", "r", stdin);
75
    freopen(".out", "w", stdout);
76
#endif
77
    ios::sync_with_stdio(0);
78
    cin.tie(0),cout.tie(0);
79

80
#ifdef MULTI_CASES
81
    cin >> T;
82
    while (T--)
83
#endif
84
       Solve();
85
    //fclose(stdin);
86
    //fclose(stdout);
87
    return 0;
88
}