|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 zhangjinxuan 于 2023-7-18 22:06 编辑
题目：https://atcoder.jp/contests/abc137/tasks/abc137_e
友好翻译（来源洛谷）：
有一个有向图，点的编号为 1~N，有 M 条边，每条边为 a i →b i ，这条边上有 c i 枚硬币。
您从节点 1 开始移动，初始硬币为 0，你需要抵达 N，经过每条边耗时 1 分钟，每次经过一条边你都能收获硬币，无论重复多少次。
当您抵达 N 节点时，你可以结束游戏，也可以继续游戏，但是当你结束游戏的时候，你需要支付 T×P 枚硬币 （T表示时间），当您的硬币少于这个值时，你需要支付全部的硬币。
你的分数就是在付款后所拥有的硬币数量，如果可以确定能获得一个最大分数，你需要输出可以获得的分数的最大值。
主要思路：
DP，感觉很奇怪。
你先别急，让我先急，首先，因为答案会减去 T * P，也就是说，走一步就会减去 P 的金币，那就把所有边权都减 P。
然后，定义状态 f j,i 表示使用 j 步走到 i 节点的最大收益。
转移就是使用 j - 1 步到达所有可以到达 i 的边 + 这条边权。
特判没有走到的情况。
处理 -1 的情况就是，如果当前走了 n 以上的步仍然在更新 f[][n] 的值，就说明不存在最大值。
码量不多，下面是我的代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
long long f[5001][2501], ans = -1ll << 60, p, z;
struct Edge {
int to;
long long l;
};
vector<Edge> edges[2501];
int main() {
scanf("%d%d%lld", &n, &m, &p);
while (m--) {
scanf("%d%d%lld", &x, &y, &z);
edges[y].push_back({x, z - p});
}
memset(f, 128, sizeof(f));
f[0][1] = 0;
for (int j = 1; j <= n + n; ++j) {
for (int i = 1; i <= n; ++i) {
for (auto k : edges[i]) {
if (f[j - 1][k.to] == f[0][0]) continue;
f[j][i] = max(f[j][i], f[j - 1][k.to] + k.l);
}
if (i == n && f[j][i] > ans) {
if (j >= n) {
puts("-1");
return 0;
}
ans = f[j][i];
}
}
}
printf("%lld\n", max(ans, 0ll));
return 0;
}
结果：https://atcoder.jp/contests/abc137/submissions/43729012
After Contest 全 WA，而且通过特殊方法，我发现 After Contest 全是 -1，是 -1 这一块没有处理好吗？
你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况下，应当输出 -1。
然而，你的代码只在 j（步数）达到或超过节点数（n）时判断是否存在负环，这并不正确。因为这样的话，可能会漏掉一些步数少于 n，但是已经形成了负环的情况。
你的负环判断应该在对每个 j 进行动态规划时都检查。如果在一个状态的硬币数量比前一个状态的硬币数量多，并且该状态所在的步数大于或等于 n，那么就可以判断存在负环。
你可以尝试将你的代码修改如下：#include <bits/stdc++.h>using namespace std;int n, m, x, y;long long f[5001][2501], ans = -1ll << 60, p, z;struct Edge { int to; long long l;};vector<Edge> edges[2501];int main() { scanf("%d%d%lld", &n, &m, &p); while (m--) { scanf("%d%d%lld", &x, &y, &z); edges[y].push_back({x, z - p}); } memset(f, 128, sizeof(f)); f[0][1] = 0; for (int j = 1; j <= n + n; ++j) { for (int i = 1; i <= n; ++i) { for (auto k : edges[ i]) { if (f[j - 1][k.to] == f[0][0]) continue; f[j][ i] = max(f[j][ i], f[j - 1][k.to] + k.l); } if (i == n) { if (j >= n && f[j][ i] > f[j - 1][ i]) { puts("-1"); return 0; } ans = max(ans, f[j][ i]); } } } printf("%lld\n", max(ans, 0ll)); return 0;}
希望这个答案可以帮助到你，如果你还有其他问题，欢迎继续提问。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-7-18 22:05:34
置顶卡
千斤顶
显身卡
发表于 2023-7-18 22:06:02
楼主
