题意
二维平面上有 n n n 个点 ( x i , y i ) (x_i, y_i) (xi,yi). 有一辆电汽车, 电池容量为 W W W, 要从点 s s s 到点 t t t. 每个点都可以充电, 充一个单位的电量需要 c i c_i ci 点花费. 一个单位的电量能走一个单位距离. 两个点之间的距离是笛卡尔距离. 开始时车在 s s s 点电量为 0 0 0, 问在充电次数不超过 Δ \Delta Δ 的情况下, 到达 t t t 点的最小花费.
1 ≤ n ≤ 1000 , 0 ≤ x i , y i ≤ 1 0 6 , 1 ≤ c i ≤ 1 0 4 , 1 ≤ W ≤ 1 0 5 , 1 ≤ Δ ≤ 10 1 \le n \le 1000, 0 \le x_i, y_i \le 10^6, 1 \le c_i \le 10^4, 1 \le W \le 10^5, 1 \le \Delta \le 10 1≤n≤1000,0≤xi,yi≤106,1≤ci≤104,1≤W≤105,1≤Δ≤10
题解
首先想到经典贪心题. 确定一条路线, 那么一定是两种选择:
- 充满电往下走
- 充到刚好到下一个点
根据这两个决策, 我们设计dp.
d p ( i , x , 0 ) dp(i, x, 0) dp(i,x,0) 表示已经充了 i i i 次电, 当前在点 x x x, 从某个点充到刚好能过来, 即现在的电量为 0 0 0.
d p ( i , x , y ) dp(i, x, y) dp(i,x,y) 表示已经充了 i i i 次电, 当前在点 x x x, 从 y y y 充满了电过来, 即现在的电量为 W − d i s t ( y , x ) W - dist(y, x) W−dist(y,x).
方程很好写:
KaTeX parse error: \cr valid only within a tabular/array environment
第一个和第三个可以 O ( n 2 ) O(n^2) O(n2)完成, 第四个也可以设 f ( i , y ) = min d p ( i − 1 , y , x ) + c y ⋅ d i s t ( z , y ) f(i, y) = \min \\{ dp(i-1, y, x) + c_y \cdot dist(z, y) \\} f(i,y)=mindp(i−1,y,x)+cy⋅dist(z,y)在 O ( n 2 ) O(n^2) O(n2)内转移 d p ( i , x , y ) = f ( i − 1 , y ) dp(i, x, y) = f(i-1, y) dp(i,x,y)=f(i−1,y)
第二个方程的优化是一个难点.
变一下型:
KaTeX parse error: \cr valid only within a tabular/array environment
然后有一个技巧. 看没变形的那个方程, 当 d i s t ( y , x ) < W − d i s t ( z , y ) dist(y, x) < W - dist(z, y) dist(y,x)<W−dist(z,y) 时, 是不会更新 d p ( i , x , 0 ) dp(i, x, 0) dp(i,x,0) 的. 运用一下排序的技巧, 如果让 d i s t ( y , x ) dist(y, x) dist(y,x) 递增, 那么"前面的"枚举对 ( x , y ) (x, y) (x,y)"能转移"的 ( W − d i s t ( z , y ) ) (W - dist(z, y)) (W−dist(z,y)), "后面的"也一定能转移. 再看变形后的方程, 里面一层的 min \min min 没有含 x x x 的参数, 我们用另一个变量 g g g 来表示里面一层 min \min min. 那么我们可以"同时枚举 z z z 和 x x x", 即"把 x x x 当成里面一层 min \min min 的 z z z". 把 ( W − d i s t ( y , z ) ) (W - dist(y, z)) (W−dist(y,z)) 和 d i s t ( y , x ) dist(y, x) dist(y,x) 放在一起排序, 即把 ( W − d i s t ( y , x ) ) (W - dist(y, x)) (W−dist(y,x)) 和 d i s t ( y , x ) dist(y, x) dist(y,x) 放在一起排序. 然后按照这个的排序顺序来枚举. 能够发现, y y y 是连接两个 min \min min 的桥梁, 所以我们把 y y y 第一维枚举, 然后对 n − 1 n-1 n−1 个 x x x (因为 x ≠ y x \ne y x=y) 的 ( W − d i s t ( y , x ) ) (W - dist(y, x)) (W−dist(y,x)) 以及 d i s t ( y , x ) dist(y, x) dist(y,x) 放在一起排序, 按照这个排序枚举这 2 ( n − 1 ) 2(n-1) 2(n−1) 个变量, 碰到 W − d i s t ( y , x ) W - dist(y, x) W−dist(y,x) 就更新 g g g, 碰到 d i s t ( y , x ) dist(y, x) dist(y,x) 就更新 d p ( i , x , 0 ) dp(i, x, 0) dp(i,x,0).
排序可以
O
(
n
2
)
O(n^2)
O(n2)预处理, 对每个
y
y
y 排这
2
(
n
−
1
)
2(n-1)
2(n−1) 个变量, 存在 vector 里, 这样就把复杂度压下来了.
由于之前是先枚举 x x x再枚举 y y y的, 后面发现要先枚举 y y y才能做这第二个方程, 然后前面写过的就乱了…总之, 注意细节, 想好再写, 否则得不偿失!
总复杂度 O ( Δ n 2 ) O(\Delta n^2) O(Δn2)
{{% code %}}
const int MAXN = 1e3+10;
const int MAXD = 15;
struct Node {
LL a;
int flag, x, y;
bool operator < (const Node &N) const {
return a == N.a ? flag == N.flag ? x == N.x ? y < y : x < N.x : flag < N.flag : a < N.a;
}
};
PII villages[MAXN];
LL dist(int i, int j) {
return LL(abs(villages[i].first - villages[j].first) + abs(villages[i].second - villages[j].second));
}
int n, s, t, W, D, c[MAXN];
LL dp[MAXD][MAXN][MAXN], f[MAXD][MAXN];
vector<Node> v[MAXN];
int main() {
scanf("%d", &n);
s = 1, t = 2;
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d%d", &x, &y, c + i);
villages[i] = {x, y};
}
scanf("%d%d", &W, &D);
memset(dp, 0x3f, sizeof(dp));
memset(f, 0x3f, sizeof(f));
dp[0][s][0] = 0;
for (int y = 1; y <= n; y++) {
for (int x = 1; x <= n; x++) if (y != x) {
v[y].push_back(Node{dist(x, y), 1, x, y});
if (dist(x, y) <= W)
v[y].push_back(Node{W - dist(x, y), 0, x, y});
}
sort(v[y].begin(), v[y].end());
}
for (int i = 1; i <= D; i++)
for (int y = 1; y <= n; y++) {
LL g = INF;
for (auto N : v[y]) {
if (N.flag && dist(y, N.x) <= W)
dp[i][N.x][0] = min(dp[i][N.x][0], g + c[y] * N.a);
else if (dp[i-1][y][N.x] < INF)
g = min(g, dp[i-1][y][N.x] - c[y] * N.a);
if (dist(y, N.x) <= W) {
f[i][N.x] = min(f[i][N.x], dp[i][N.x][y] + c[N.x] * dist(N.x, y));
dp[i][N.x][y] = f[i-1][y];
dp[i][N.x][y] = min(dp[i][N.x][y], dp[i-1][y][0] + c[y] * W);
dp[i][N.x][0] = min(dp[i][N.x][0], dp[i-1][y][0] + c[y] * dist(N.x, y));
}
}
}
LL ans = INF;
for (int i = 1; i <= D; i++)
ans = min(ans, dp[i][t][0]);
printf("%lld\n", ans < INF ? ans : -1);
return 0;
}
{{% /code %}}