Yuilice的题解

题目大意

在一个一维的地图$p$当中进行行走，每一个格子上都有下一个前往方向的对应坐标$p_i$，只能顺着格子给定的坐标行走。

在地图当中，可以选择行走或者不行走，但是无论如何，在一步之后，都会附加上当前对应格子的分数$a_i$.

给定两个人的起点，求解最大分数为多少，谁大一点。

思路分析

​ 当你从一个顶点出发的时候，你有两个选择，分别是停留和行走，两个选择带来的收益也是不同的。假如你要去求在一个路线当中的所有状态和收益，那么你就需要去枚举出所有的情况。

​ 但是假如你要去枚举所有的情况，那么一个人的情况总数就是$2^n$，在这里$n$最大为$2 \times 10^5$因此肯定不可能实现，所以要则优。

​ 根据贪心原则，如果需要获得最大的分数，那么并且可以在有停留的选择的情况下，一个人能够行走的格子肯定是有限的，最多也就走$n$个格子，那么只需要找到最大的分数的格子，一直呆在那里，即可完成最值得计算。

​ 如何去寻找最大分数的格子？可以采用DFS去在地图上行走。

​ $it -> p[it]$ 即可。

​ 同时不需要一直行走，避免重复走格子，还需要打个标记。

​ $vis[it] = true$

​ 因为你在没有枚举完所有格子之前，你是不知道哪个最大，并且到达最大之前的分数是多少的，所以一定会遍历$n$个格子求得到达最大之前的状态。

​ 假如你到达了最大的格子坐标$Max_{it}$，就没有必要一直呆在原地累加了，直接通过算式$(T - step) * a_i$求得剩下时间能够获取的总价值即可。

​ 最终，枚举到达n个格子的所有状态，取最值，判断大小即可。

时间复杂度分析

$O(min(T,n))$

代码示范

#include<bits/stdc++.h>
using namespace std;
long long score(vector<int>&p,vector<int>&a,int s,int k){
	int n=p.size();
	long long mx=0,cur=0;
	vector<bool>vis(n);
	while(!vis[s]&&k>0){
		vis[s]=1;
		mx=max(mx,cur+1ll*k*a[s]);
		cur+=a[s];
		k--;
		s=p[s];
	}
	return mx;
}
int main(){
	int t;
	t = 1; 
//	cin>>t;
	while(t--){
		int n,k,s1,s2;
		cin>>n>>k>>s1>>s2;
		vector<int>p(n),a(n);
		for(auto&e:p){
			cin>>e;
			e--;
		}
		for(auto&e:a){
			cin>>e;
		}
		long long A=score(p,a,s1-1,k),B=score(p,a,s2-1,k);
		cout<<(A>B?"YuiliceSeko!\n":A<B?"Nononononomeo~\n":"Okay,fine.\n");
	}
}

——Yuilice