自动搬运

查看原文

来自洛谷，原作者为

	奇米 **

搬运于2025-08-24 22:16:26，当前版本为作者最后更新于2020-01-26 09:04:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解-P6005 Time is Mooney G

• 题目意思

就是给你一个有向图，你在上面走，没经过一个点可以获得$m_i$，最后你要减去$sum^2$(走过的边数)$*C$

• $Sol$

考虑$DP$,我们设$f_{i,j}$表示第$i$天到达城市$j$的最大收益。

转移很简单$f_{i,j}=max\{f_{i-1,las_j}+m_j,f_{i,j}\}$

对于$las_j$的处理我们只需要反向建有向边即可，答案就是$max\{f_{i,1}-i^2*C\}$

但是这样$i$的枚举范围无法确定，但是我们发现$i\leq 1000$即可，因为$max\{m_i\}*day-day^2*C\leq 1$

• $Code$

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

const int N=1005;

int n,m,C,cnt,head[N];
int M[N],f[N][N],ans; 

struct nood {
	int nex,to;
};
nood e[N<<2];

inline void jia(int u,int v) {
	e[++cnt].nex=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}

inline int read() {
	int sum=0; char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) 
		sum=sum*10+(ch^48),ch=getchar();
	return sum;
}

int main() {
	n=read();
	m=read();
	C=read();
	for ( int i=1;i<=n;i++ ) M[i]=read();
	for ( int i=1;i<=m;i++ ) {
		int u,v;
		u=read();
		v=read();
		jia(v,u);
	}
	//f[i][j]表示第i天到达第j座城市的最大收益
	memset(f,-1,sizeof(f));
	f[0][1]=0;
	for ( int i=1;i<=1000;i++ ) {
		for ( int j=1;j<=n;j++ )
			for ( int k=head[j];k;k=e[k].nex ) {
				int v=e[k].to;
				if(~f[i-1][v]) 
					f[i][j]=max(f[i][j],f[i-1][v]+M[j]);
			}
		if(ans<f[i][1]-C*i*i) ans=f[i][1]-C*i*i;
	}
	printf("%d\n",ans);
	return 0;
}