[补题记录] Atcoder Beginner Contest 325（E、F）
URL：https://atcoder.jp/contests/abc325
目录
E
Problem/题意
Thought/思路
Code/代码
F
Problem/题意
Thought/思路
Code/代码
E
Problem/题意
有一个二维矩阵，D[i][j] 表示从 i 到 j 的距离。从 i 到 j 有两种方式：
- 坐汽车：耗费 D[i][j] * A；
- 坐火车：耗费 D[i][j] * B + C；
你可以选择在某个城市 i 换乘火车，但不能再从火车换乘汽车。问最少的时间。
Thought/思路
恼馋题目，使我的 rank 旋转。
最重要的是理解这句话，然后做两个反向的最短🦌即可。
Code/代码
#include "bits/stdc++.h"#define int long longconst int inf = 1e15;int n, a, b, c, d[1007][1007], dis1[1000007], dis2[1000007];void dij(int s, int* dis) {for (int i = 1; i <= 1000000; ++ i) dis[i] = inf;dis[s] = 0;std::queue <int> q;q.push(s);while (!q.empty()) {int i = q.front(); q.pop();for (int j = 1; j <= n; ++ j) {int w = (s == 1 ? d[i][j] * a : d[i][j] * b + c);if (dis[j] > w + dis[i]) {dis[j] = w + dis[i];q.push(j);}}}
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);std::cin >> n >> a >> b >> c;for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= n; ++ j) {std::cin >> d[i][j];}}dij(1, dis1);dij(n, dis2);int ans = inf;for (int i = 1; i <= n; ++ i){ans = std::min(dis1[i] + dis2[i], ans);}std::cout << ans;}F
Problem/题意
有 N 条传输带需要监控，每条传输带长度为 D[i]，现在有两种监控可以选择：
- 第一种：监控长度为 L[1]，售价 C[1]；
- 第二种：监控长度为 L[2]，售价 C[2]；
要求：
- 对于传输带 D[i]，所选的监控可以覆盖其长度；
- 每种监控的购买数量不能超过 K[1]、K[2]；
问是否能保证 N 条传输带都能被完整监控，若能，最小代价是多少。
Thought/思路
这个题要求维护最小值以及类似背包的最大数量。
通常我们在背包中，dp 表示最大价值，但在这个题中，多了一个 K 需要维护。
再想到，如果知道了某个状态下的 K[1]、K[2]，其实就能求出这个状态下的价值。
因此，我们可以把 K2 当作 dp 表示的值，维护 K1 不超过限制的情况下，K2 的最少数量。
因此，dp[i][j] 表示：前 i 个，一共使用了 j 个一类监控，所需要的最少二类监控的数量。
Code/代码
#include "bits/stdc++.h"#define int long longconst int inf = 1e15;int n, d[100007], dp[107][1007];
std::array <int, 3> l, c, k;signed main() {std::cin >> n;for (int i = 1; i <= n; ++ i) {std::cin >> d[i];for (int j = 0; j <= 1000; ++ j) {dp[i][j] = inf;}}std::cin >> l[1] >> c[1] >> k[1];std::cin >> l[2] >> c[2] >> k[2];for (int i = 1; i <= n; ++ i) {for (int j = 0; j <= k[1]; ++ j) { // 总共用了 j 个 K1for (int k = 0; k <= j; ++ k) { // j 与 k 做差，得出第 i 个用了几个 K1int p = j - k;int a = (d[i] - p * l[1] <= 0 ? 0 : d[i] - p * l[1]);dp[i][j] = std::min(dp[i][j], dp[i - 1][k] + (a % l[2] == 0 ? a / l[2] : a / l[2] + 1));}}}int ans = inf;for (int i = 0; i <= k[1]; ++ i) {if (dp[n][i] <= k[2]) {ans = std::min(i * c[1] + dp[n][i] * c[2], ans);}}if (ans == inf) std::cout << -1;else std::cout << ans;
}