2020-2021 ACM-ICPC Asia Seoul Regional Contest D.Electric Vehicle @ Wings            分类 ACM
发布于 星期四, 二月 18 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

二维平面上有 $n$ 个点$(x_i, y_i)$. 有一辆电汽车, 电池容量为 $W$, 要从点 $s$ 到点 $t$. 每个点都可以充电, 充一个单位的电量需要 $c_i$ 点花费. 一个单位的电量能走一个单位距离. 两个点之间的距离是笛卡尔距离. 开始时车在 $s$ 点电量为 $0$, 问在充电次数不超过 $\Delta$ 的情况下, 到达 $t$ 点的最小花费.

$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. 充满电往下走
  2. 充到刚好到下一个点

根据这两个决策, 我们设计dp.

$dp(i, x, 0)$ 表示已经充了 $i$ 次电, 当前在点 $x$, 从某个点充到刚好能过来, 即现在的电量为 $0$.

$dp(i, x, y)$ 表示已经充了 $i$ 次电, 当前在点 $x$, 从 $y$ 充满了电过来, 即现在的电量为 $W - dist(y, x)$.

方程很好写:

$$ \begin{aligned} dp(i, x, 0) &= \min_{y \ne x}^{dist(y, x) \le W} \{ dp(i-1, y, 0) + c_y \cdot dist(y, x) \} \newline dp(i, x, 0) &= \min_{y, z \ne x}^{dist(z, y) \le W, W - dist(z, y) \le dist(y, x)} \{ dp(i-1, y, z) + c_y \cdot (dist(y, x) - (W - dist(z, y))) \} \newline dp(i, x, y) &= \min_{y \ne x}^{dist(y, x) \le W} \{ dp(i-1, y, 0) + c_y \cdot W \} \newline dp(i, x, y) &= \min_{y, z \ne x}^{dist(y, x) \le W} \{ dp(i-1, y, z) + c_y \cdot dist(z, y) \} \end{aligned} $$

第一个和第三个可以$O(n^2)$完成, 第四个也可以设$f(i, y) = \min \{ dp(i-1, y, x) + c_y \cdot dist(z, y) \}$在$O(n^2)$内转移$dp(i, x, y) = f(i-1, y)$

第二个方程的优化是一个难点.

变一下型:

$$ \begin{aligned} dp(i, x, 0) &= \min_{y, z \ne x}^{dist(z, y) \le W, W - dist(z, y) \le dist(y, x)} \{ dp(i-1, y, z) + c_y \cdot (dist(y, x) - (W - dist(z, y))) \} \newline &= \min_{y \ne x}^{dist(y, x) \le W} \{ \min_{z \ne y}^{dist(z, y) \le W} \{ dp(i-1, y, z) - c_y \cdot (W - dist(y, z)) \} + c_y \cdot dist(y, x) \} \end{aligned} $$

然后有一个技巧. 看没变形的那个方程, 当 $dist(y, x) < W - dist(z, y)$ 时, 是不会更新 $dp(i, x, 0)$ 的. 运用一下排序的技巧, 如果让 $dist(y, x)$ 递增, 那么"前面的"枚举对$(x, y)$“能转移"的 $(W - dist(z, y))$, “后面的"也一定能转移. 再看变形后的方程, 里面一层的 $\min$ 没有含 $x$ 的参数, 我们用另一个变量 $g$ 来表示里面一层 $\min$. 那么我们可以"同时枚举 $z$ 和 $x$”, 即"把 $x$ 当成里面一层 $\min$ 的 $z$”. 把$(W - dist(y, z))$ 和 $dist(y, x)$ 放在一起排序, 即把 $(W - dist(y, x))$ 和 $dist(y, x)$ 放在一起排序. 然后按照这个的排序顺序来枚举. 能够发现, $y$ 是连接两个 $\min$ 的桥梁, 所以我们把 $y$ 第一维枚举, 然后对 $n-1$ 个 $x$ (因为 $x \ne y$) 的 $(W - dist(y, x))$ 以及 $dist(y, x)$ 放在一起排序, 按照这个排序枚举这 $2(n-1)$ 个变量, 碰到 $W - dist(y, x)$ 就更新 $g$, 碰到 $dist(y, x)$ 就更新 $dp(i, x, 0)$.

排序可以$O(n^2)$预处理, 对每个 $y$ 排这 $2(n-1)$ 个变量, 存在 vector 里, 这样就把复杂度压下来了.

由于之前是先枚举$x$再枚举$y$的, 后面发现要先枚举$y$才能做这第二个方程, 然后前面写过的就乱了…总之, 注意细节, 想好再写, 否则得不偿失!

总复杂度$O(\Delta n^2)$

代码
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;
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球
  • 三阶速拧20s

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch