题解 P6005 Time is Mooney G

题解-P6005 Time is Mooney G

• 题目意思

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

• 

  考虑,我们设表示第天到达城市的最大收益。

  转移很简单

  对于的处理我们只需要反向建有向边即可，答案就是

  但是这样的枚举范围无法确定，但是我们发现即可，因为

• 

#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;
}