#C241031B. CF2023B-Skipping

标签（Label）

最短路算法
思维
图论转化

网址（Website）

Problem - B - Codeforces

Problem - D - Codeforces

Skipping - 洛谷

题目（Problem）

现在已经是 $3024$ 年，问题的创意早已枯竭，奥林匹克竞赛现在以修改后的个人形式进行。奥林匹克竞赛由 $n$ 个问题组成，编号从 $1$ 到 $n$ 。 $i$ -问题有自己的分数 $a_i$ 和一定的参数 $b_i$ 。( $1 \le b_i \le n$ ).

最初，测试系统会给参与者第 $1$ 个问题。当参与者得到第 $i$ 个问题时，他们有两个选择：

他们可以提交问题并获得 $a_i$ 分；
他们可以跳过这个问题，在这种情况下，他们将永远无法提交这个问题。

然后，测试系统会从指数为 $j$ 的问题中为参与者选择下一个问题，这样，参与者就可以得到 $a_i$ 分：

如果他提交了第 $i$ 个问题，系统就会查看索引为 $j\le i$ 的问题；
如果他跳过了第 $i$ 个问题，则会查看索引为 $j \leq b_i$ 的问题。

在这些问题中，它会选择一个索引最大的问题，这个索引以前没有给过参与者(他以前既没有提交也没有跳过这个问题)。如果没有这样的问题，那么该参赛者的比赛结束，其成绩等于所有提交问题的分数总和。特别是，如果参赛者提交了第一个问题，那么他们的比赛就结束了。需要注意的是，参赛者最多只能收到每个问题最多 $1$ 次。

普罗克霍尔已经为奥林匹克竞赛做了充分准备，现在他可以提交任何问题。请帮助他确定他能获得的最高分数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $t$ ( $1 \leq t \leq 10^5$ ) - 测试用例数。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 4 \cdot 10^5$ ) - 奥林匹克竞赛中的问题数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) - 问题的得分。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ( $1 \leq b_i \leq n$ ) - 问题的参数。

保证所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$ 。

输出

对于每个测试用例，输出一个整数 - Prokhor 能达到的最大点数。

样例输入

4
2
15 16
2 1
5
10 10 100 100 1000
3 4 1 1 1
3
100 49 50
3 2 2
4
100 200 300 1000
2 3 4 1

样例输出

注

在第一个测试案例中，Prokhor 可以跳过第一个问题；然后他将收到索引为 $b_1 = 2$ 的问题。Prokhor 可以提交该问题并获得 $a_2 = 16$ 分。之后，比赛将结束，因为 Prokhor 已经收到了所有问题。请注意，如果普罗克霍尔提交了第一个问题，他将得到 $a_1 = 15$ 分，但比赛将立即结束。

在第二个测试案例中，Prokhor 可以跳过第一个问题，然后他将收到索引为 $b_1 = 3$ 的问题。Prokhor 可以提交该问题并获得 $a_3 = 100$ 分。之后，Prokhor 将收到第二个问题，他可以跳过这个问题，收到索引为 $b_2 = 4$ 的问题。Prokhor 可以提交第四个问题，并再次获得 $a_4 = 100$ 分。之后，比赛结束，因为 Prokhor 已经收到了索引不超过 $4$ 的所有问题。因此，普罗克霍尔将总共得到 $200$ 分。

在第三个测试案例中，Prokhor 可以提交第一个问题并获得 $100$ 分，之后比赛将立即结束。

题解（Solution）

转换为图论来解决：

做完一道题之后，向前面一道题连边，即 $i\to i-1$ ，没有代价；
跳过这道题，向后面的点连边，即 $i\to b_i$ ，代价为 $a_i$ ；

要求的就是最小的代价，最后的答案为 $\max_{i=1}^{i\le n}\left(\left(\sum_{j=1}^{j\le i}a_j\right)-dis_i\right)$ 。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 401234;
bool ST;

int n,a[N],b[N];

priority_queue<P> q;
int dis[N];
vector<P> ft[N];
void dijkstra(int st){
	fill(dis,dis+n+1,inf);
	dis[st] = 0, q.emplace(0,st);
	while(q.size()){
		int x=q.top().y;q.pop();
		for(auto p:ft[x]){
			int y,v;tie(y,v)=p;
			if(dis[x]+v<dis[y]){
				dis[y] = dis[x]+v;
				q.emplace(-dis[y],y);
			}
		}
	}
}

void Solve(){
	For(i,1,n) ft[i].clear();
	n = rd();For(i,1,n) a[i] = rd();For(i,1,n) b[i] = rd();
	For(i,2,n) ft[i].emplace_back(i-1,0);
	For(i,1,n) ft[i].emplace_back(b[i],a[i]);
	dijkstra(1);int ans = 0, leijia = 0;
	For(i,1,n) leijia+=a[i],ans = max(ans, leijia-dis[i]);
	cout<<ans<<'\n';
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = rd();double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}