P6005 [USACO20JAN] Time is Mooney G 题解

题目描述

Bessie 正在安排前往牛尼亚的一次出差，那里有 \(N\)（\(2 \leq N \leq 1000\)）个编号为 \(1 \ldots N\) 的城市，由 \(M\)（\(1 \leq M \leq 2000\)）条单向的道路连接。Bessie 每次访问城市 \(i\) 都可以赚到 \(m_i\) 哞尼（\(0 \leq m_i \leq 1000\)）。从城市 \(1\) 出发，Bessie 想要赚到尽可能多的哞尼，最后回到城市 \(1\)。为了避免争议，\(m_1=0\)。

沿着两个城市之间的道路移动需要消耗一天。出差的准备工作十分费钱；旅行 \(T\) 天需要花费 \(C \times T^2\) 哞尼（\(1 \leq C \leq 1000\)）。

Bessie 在一次出差中最多可以赚到多少哞尼？注意有可能最优方案是 Bessie 不访问城市 \(1\) 之外的任何城市，在这种情况下结果应当为 \(0\)。

输入格式

输入的第一行包含三个整数 \(N\)、\(M\) 和 \(C\)。
第二行包含 \(N\) 个整数 \(m_1,m_2,\ldots, m_N\)。
以下 \(M\) 行每行包含两个空格分隔的整数 \(a\) 和 \(b\)（\(a \neq b\)），表示从城市 \(a\) 到城市 \(b\) 的一条单向道路。

输出格式

输出一行，包含所求的答案。

分析

这道题可以用动态规划解决。我们设 \(dp_{i,j}\) 为在第 \(i\) 天 \(j\) 号城市的最大哞尼获得数（不包括旅游花费 \(C \times T^2\) 的那一部分）。我们枚举每个开始时间 \(t\) 而同时在的位置 \(s\)。因为最大的 \(N\)（城市数）小于等于 \(1000\)，所以 \(t\) 的枚举范围上限为 \(0\) ~ \(2000\)（往返 \(1000\) 个城市）。显然，\(s\) 的枚举范围为 \(1\) ~ \(N\)。

如果在 \(t\) 的前一天没有到 \(s\) 城市（即 dp[t-1][s] == -inf），那就忽略这次循环。否则遍历与其相邻的所有城市，根据状态转移方程更新数组。

状态转移方程：在原来的 \(dp_{t,j}\) 和 \(dp_{t-1,s} + m_j\)（上一次走的最大值加上这次走的收益）之中找到最大，即

\[dp_{t,j} = \max(dp_{t,j}, dp_{t-1,s} + m_j) \]

如果一个 \(dp_{t,1}\) 不是空（inf），那么就说明这条路可以原路返回城市 \(1\)。那么这条路可行。我们创建一个变量 \(\text{mx}\) 存储最大结果，比较 \(\text{mx}\) 是否小于找到的 \(dp_{t,1}\) 去掉旅游花费（\(C\times T^2\)）并更新结果即可。

给出代码：

......
const int inf = 0x7f7f7f7f;
int N, M, C, m[1005], dp[2005][2005];
vector<int> g[3005];int main(void){cin >> N >> M >> C;for(int i=1; i<=N; ++i)cin >> m[i];for(int i=1, a, b; i<=M; ++i){cin >> a >> b;g[a].push_back(b);}memset(dp, -inf, sizeof dp);dp[0][1] = 0; // 刚开始肯定为 0int mx = 0;for(int t=1; t<=2000; ++t){for(int s=1; s<=N; ++s){if (dp[t-1][s] == -inf) continue; // 如果在 t-1 秒没有到达 s，跳过该循环for(int j : g[s]) // 每一个邻居 jdp[t][j] = max(dp[t][j], dp[t-1][s] + m[j]);}if (dp[t][1] != -inf) // 如果能回到城市 1mx = max(mx, dp[t][1] - C * t * t);}cout << mx << endl;return 0;
}

有问题可以评论提出改正。