正经题解｜得分游戏

题目大意

在一个一维的地图$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");
	}
}

#include<bits/stdc++.h>
using namespace std;

long long ans1, ans2;
	int n,pb,ps,k;
bool vis[200005];

long long a[200005];
long long b[200005];

void dfs1(int it,int step,long long  answer){
	// cout << it << endl;
	vis[it] = true;
	if(step >= k){
		ans1 = max(ans1,answer);
		return ;
	}
	if(!vis[a[it]])
		dfs1(a[it],step+1,answer+b[a[it]]);
	ans1 = max(ans1,answer + (k - step) * b[it]);
}
void dfs2(int it,int step,long long  answer){
	vis[it] = true;
	if(step >= k){
		ans2 = max(ans2,answer);
		return ;
	}
	if(!vis[a[it]])
		dfs2(a[it],step+1,answer+b[a[it]]);
	ans2 = max(ans2,answer + (k - step) * b[it]);
}

void solve()
{
	
	ans1 = ans2 = 0 ;
	cin >> n >> k >> pb >> ps ;
	for(int i = 1 ; i <= n ; i ++ ){
		cin >> a[i];
	}
	for(int i = 1 ; i <= n ; i ++ ){
		cin >> b[i];
	}
	memset(vis,0,sizeof vis);
	dfs1(pb,1,b[pb]);
	memset(vis,0,sizeof vis);
	dfs2(ps,1,b[ps]);
	if(ans1 > ans2)cout << "YuiliceSeko!" << endl;
	else if( ans1 < ans2)cout << "Nononononomeo~" << endl;
	else cout << "Okay,fine." << endl;
	// cout << ans1 << " " << ans2 << endl;
}

int main()
{
	int t=1;
//	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}