Eating Everything Efficiently(反向dp)

取最大值即可。用拓扑，dfs都可以实现

#include <bits/stdc++.h>

using namespace std;

const int maxn=500009;

int n,m;

struct p{

	int to,nxt;

}d[maxn];int head[maxn],cnt=1;

void add(int u,int v){

	d[cnt].nxt=head[u],d[cnt].to=v,head[u]=cnt++;

}

double ans=0,dp[maxn],val[maxn];

void dfs(int now)

{

	if(dp[now])	return;

	dp[now]=0;

	for(int i=head[now];i;i=d[i].nxt)

	{

		int v=d[i].to;

		dfs(v);

		dp[now]=max(dp[now],dp[v]);

	}

	dp[now]=max(val[now]+dp[now]/2.0,dp[now]);

	ans=max(ans,dp[now]);

}

int main()

{

	cin>>n>>m;

	for(int i=1;i<=n;i++)	cin>>val[i];

	for(int i=1;i<=m;i++)

	{

		int l,r;

		cin>>l>>r;l++,r++;

		add(l,r);

	}

	dfs(1);

	printf("%.6lf",ans);

}

巴特西

Eating Everything Efficiently(反向dp)

最新文章

热门文章