Time is Mooney (USACO Gold 2020 January)

比较简单的一个DP题。首先直观来看，时间越长，时长带来的penalty越大，是个平方关系。所以比较容易想到，旅行时长是有一个最大值的，简单推一下不等式（赚的钱必须大于0）：

m \cdot t \geq C \cdot t^2 \\ t \leq m / C

其中 $m$ 是 $\max m_i$ 。所以最大时长 $T_\text{max} = m / C$ 。

因为 $m \leq 1000$ ，所以时长最大不会超过 $1000$ ， $N$ 也比较小 $1000$ 。然后我们定义 $\text{dp}[i][j]$ : 第 $i$ 天，到达城市 $j$ 的情况下，最多能赚到最多多少钱。然后状态转换比较简单就不写了。

复杂度 $\mathcal{O}(T_{\text{max}} \cdot (N+M))$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// n <= 1000, m <= 2000, c <= 1000
int n, m, c;
vector<int> adj[1005];
int a[1005];
int dp[1005][1005];     // dp[i][j], at day i, at city j, max money earned 
ll ans;
 
int main() {
    scanf("%d %d %d", &n, &m, &c);
    int amax = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        amax = max(amax, a[i]);
    }
    for (int i = 0; i < m; i++) {
        int a,b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
    }
    for (int i = 0; i <= 1000; i++)
        for (int j = 0; j <= 1000; j++)    
            dp[i][j] = INT32_MIN;
    dp[0][1] = 0;
 
    // amax * i >= c * i^2, so i <= amax / c
    int tmax = amax / c;
    for (int i = 0; i <= tmax && i <= 1000; i++)
        for (int j = 1; j <= n; j++)
            for (int k: adj[j]) {
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[k]);
                if (k == 1)
                    ans = max(ans, (ll)dp[i+1][k] - c*(i+1)*(i+1));
            }
    printf("%lld", ans);
 
    return 0;
}