第一个题解

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m, c, ans;
int arr[1005];
struct perEdge{
    int to;
    int next;
} edge[2005];
int ei, vertex[1005];
int dp[1005][1005];

void add(int u, int v){
    ei += 1;
    edge[ei].to = v;
    edge[ei].next = vertex[u];
    vertex[u] = ei;
}

int main(){
    cin >> n >> m >> c;
    for (int i=1; i<=n; i++) cin >> arr[i];
    for (int i=1, u, v; i<=m; i++){
        cin >> u >> v;
        add(v, u);  // 反向建边
    }

    // dp[i][j]表示第i天走到第j天的最大收益
    memset(dp, -1, sizeof dp);
    dp[0][1] = 0;  // 根据题意可得
    // 枚举天数
    for (int i=1; i<=1000; i++){
        for (int j=1; j<=n; j++){
            int index = vertex[j];
            while(index){
                int to = edge[index].to;
                if (dp[i-1][to] != -1)
                    dp[i][j] = max(dp[i][j], dp[i-1][to] + arr[j]);
                index = edge[index].next;
            }
        }
        ans = max(ans, dp[i][1] - c * i * i);
    }
    cout << ans << endl;
    return 0;
}