题意

给出一个有向图，走到每个节点有 \(m_i\) 的收益，每一条边要走一天，走 \(T\) 天的花费是 \(C\cdot T^2\)，求从节点 \(1\) 开始并且在节点 \(1\) 结束的旅行的最大利润？（利润等于收益减去花费）

另外也可以不进行旅行，即零利润。

题解

注意到收益是线性增长，而花费是指数级增长，因此花费将逐渐超过收益。

以收益均为 \(1000\)，\(C=1\) 为例，即收益最大化，成本最小化，运行时间最长。

可见 \(T=\sqrt{1000}\) 为最大值，可视为常数

那么这题的时间复杂度就是 \(O(nm)\) 了，在有利益的情况下拓展即可。

Code

#include<cstdio>

#include<cstring>

#include<algorithm>

const int MAXN=1000+5;

struct Edge{int u,v,next;};

long long dp[MAXN*2][MAXN];int n,m,p,c[MAXN],cnt,head[MAXN];Edge edge[MAXN*2],tmp[MAXN*2];

bool comp(Edge a,Edge b) {return c[a.v]<c[b.v];}

void AddEdge(int u,int v)

{

//	printf("Add %d %d\n",u,v);

	edge[++cnt].u=u;edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt;

}

int main()

{

	freopen("time.in","r",stdin);

	freopen("time.out","w",stdout);

	scanf("%d %d %d",&n,&m,&p);

	int cmax=0;

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

	{

		scanf("%d",&c[i]);

		cmax=std::max(cmax,c[i]);

	}

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

		scanf("%d %d",&tmp[i].u,&tmp[i].v);

	std::sort(tmp+1,tmp+m+1,comp);

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

		AddEdge(tmp[i].u,tmp[i].v);

	memset(dp,-0x3f3f3f,sizeof(dp));

	dp[0][1]=0;

	int i=0;bool moved=1;

	while(moved)

	{

		moved=0;

		int addcost=p*((i+1)*(i+1)-i*i);

		if(addcost>cmax) break;

		for(int j=1;j<=n;j++)

			if(dp[i][j]>=0)

				for(int k=head[j];k;k=edge[k].next)

				{

					//if(addcost<=c[edge[k].v])

					{

						//printf("Day %d From %d to %d, New: %lld\n",i,j,edge[k].v,std::max(dp[i+1][k],dp[i][j]+c[edge[k].v]-addcost));

						dp[i+1][edge[k].v]=std::max(dp[i+1][edge[k].v],dp[i][j]+c[edge[k].v]-addcost);

						moved=1;

					}

				}

		i++;

	}

	long long ans=0;

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

		ans=std::max(ans,dp[p][1]);

	printf("%lld\n",ans);

	return 0;

}

巴特西

USACO January Contest Gold Time is Mooney 题解

题意

题解

Code

最新文章

热门文章