NC222462. [USACOJan2020G]TimeisMooney
描述
输入描述
The first line contains three integers N, M, and C.
The second line contains the N integers m1,m2,…mN.
The next M lines each contain two space-separated integers a and b (a≠b) denoting a one-way road from city a to city b.
输出描述
A single line with the answer.
示例1
输入:
3 3 1 0 10 20 1 2 2 3 3 1
输出:
24
说明:
The optimal trip is 1→2→3→1→2→3→1. Bessie makes 10+20+10+20−1⋅62=24 moonies in total.C++ 解法, 执行用时: 9ms, 内存消耗: 444K, 提交时间: 2021-11-10 12:24:55
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
typedef long long LL;
const int NN = 1004;
struct Edge {
int u, v;
};
LL D[2][NN];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
LL N, M, C;
cin >> N >> M >> C;
vector<int> V(N + 1);
vector<Edge> E(M);
_for(i, 1, N + 1) cin >> V[i];
_for(i, 0, M) cin >> E[i].u >> E[i].v;
memset(D, -1, sizeof D), D[0][1] = 0;
LL ans = 0;
for (int t = 1; t <= NN; t++) {
int p = t % 2;
memset(D[p], -1, sizeof D[p]);
for (auto &e : E)
if (D[1 - p][e.u] >= 0)
D[p][e.v] = max(D[p][e.v], D[1 - p][e.u] + V[e.v]);
ans = max(ans, D[p][1] - C * t * t);
}
cout << ans << endl;
}