D. Skipping 【 Codeforces Round 980 (Div. 2)】
D. Skipping
思路:
注意到最佳策略是先往右跳转到某处,然后按顺序从右往左把没有遇到过的题目全部提交。
将从 i i i跳转到 b [ i ] b[i] b[i]视为通过边权(代价)为 a [ i ] a[i] a[i]的路径,而向左的路径边权都是 0 0 0;目的是找到到从出发点到每个点 i i i的最短路径(最小代价) d [ i ] d[i] d[i],用Dijkstra跑一遍即可。
得分即为前缀和 p r e [ i ] pre[i] pre[i]-代价 d [ i ] d[i] d[i],将 i i i从 1 1 1遍历到 n n n,取 m a x max 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;
}