题意
从 \(1\) 开始决策，若选当前数，则累计贡献 \(a[i]\) 并跳到 \(j\) 位置，\(j\) 是 \(\lt i\) 且没有决策过（包括选了和没选）的最大位置（操作 \(1\)）。若不选当前数，则跳转到 \(j\) 位置，\(j\) 是 \(\le b[i]\) 且没有决策过（包括选了和没选）的最大位置（操作 \(2\)）。求最大得分。
思路
看到的第一眼以为是动态规划，想了一下觉得dp顺序太难搞了，好像也会有后效性。（但据说dp能做？）
考场上猜了一个结论：应该可以找一个拐点，到达之后就一直用操作 \(1\)。下来一看这个结论是对的。
感性理解一下，就是用操作 \(2\) 一定是为了能拿更远处的数，当操作 \(2\) 不再优后，我们只用操作 \(1\) 就是最优的。
设我们用操作 \(2\) 放弃了 \(p_1,p_2,\dots,p_m\)，最后拐点是 \(i\)。（也是最远点，因为不是最远点的话肯定不优）
所以答案就是 \(\max_{1 \le i \le n} presum[i] - \sum_{1 \le j \le m}a[p_j]\)。
现在问题转化成了对于每个 \(i\)，我们要最小化 \(\sum_{1 \le j \le m}a[p_j]\)，即 “放弃贡献”。
这些点并不是按编号大小依次放弃的，也存在顺序问题，考虑构图。
我们连边 \((i \to i - 1, 0), (i \to b[i], a[i])\)。最后得到一张带权有向图。
用 \(dijkstra\) 跑一遍，\(dis[i]\) 就是最小的 “放弃贡献”。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
#define int ll
using namespace std;
using ll = long long;
const int N = 4e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
struct node{
int v, w, ne;
}e[N << 1];
int T, n, idx = 0;
int a[N], b[N], dis[N], sm[N], first[N];
bool vis[N];
void add(int x, int y, int z){
e[++ idx] = (node){y, z, first[x]};
first[x] = idx;
}
priority_queue<pair<int, int> > q;
int solve(){
cin >> n;
F(i, 1, n) first[i] = vis[i] = 0, dis[i] = inf;
dis[1] = idx = 0;
F(i, 1, n) cin >> a[i], sm[i] = sm[i - 1] + a[i];
F(i, 1, n) cin >> b[i], add(i, b[i], a[i]);
F(i, 2, n) add(i, i - 1, 0);
q.push({0, 1});
while(q.size()){
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = first[u]; i; i = e[i].ne){
int v = e[i].v, w = e[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
q.push({-dis[v], v});
}
}
}
int mx = 0;
F(i, 1, n) mx = max(mx, sm[i] - dis[i]);
return mx;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
while(T --){
cout << solve() << '\n';
}
return fflush(0), 0;
}
总结
首先是要大胆猜结论，好验证的话就拿小样例验证一下，更重要的是利用这个性质做进一步的处理。
对于转移顺序没有明显规律，视具体数据的题，考虑构图。
遇到最大化问题，尝试转成最小化问题，或许就会有更多发挥空间，比如用 dijkstra 跑最短路，二分之类的。
参考博客
Codeforces Round #980 Editorial - Codeforces
Codeforces Round 980 div2 个人题解(A~D) - ExtractStars - 博客园
标签：le,int,cin,mx,操作,CF980,Div2,dis From： https://www.cnblogs.com/superl61/p/18516678