D. Skipping 【 Codeforces Round 980 (Div. 2)】

D. Skipping

思路:

注意到最佳策略是先往右跳转到某处，然后按顺序从右往左把没有遇到过的题目全部提交。
将从$i$跳转到$b[i]$视为通过边权(代价)为$a[i]$的路径，而向左的路径边权都是$0$；目的是找到到从出发点到每个点$i$的最短路径（最小代价)$d[i]$，用Dijkstra跑一遍即可。
得分即为前缀和$pre[i]$-代价$d[i]$，将$i$从$1$遍历到$n$，取$max$即为最终答案。

代码:

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;void solve() {int n;cin >> n;int a[n + 1];for (int i = 1; i <= n; i++) {cin >> a[i];}vector<vector<pii>> lj(n + 1);for (int i = 1; i <= n; i++) {int b;cin >> b;lj[i].push_back({a[i], b});if (i != 1) lj[i].push_back({0, i - 1});}vector<bool> vis(n + 1, false);vector<int> d(n + 1, 1e15);priority_queue<pii, vector<pii>, greater<pii>> pq;pq.push({0, 1});d[1] = 0;while (!pq.empty()) {pii top = pq.top();pq.pop();int td = top.first;int tg = top.second;if (vis[tg])continue;vis[tg] = true;for (pii e : lj[tg]) {int ng = e.second;int nd = e.first;if (d[ng] > td + nd) {d[ng] = td + nd;pq.push({td + nd, ng});}}}int sum = 0, ans = 0;for (int i = 1; i <= n; i++) {sum += a[i];ans = max(ans, sum - d[i]);}cout << ans << endl;
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}