1 条题解
-
0
[B] Frog 2(dp_b)题解
题意简述
与 Frog 1 相同,但每次可跳 格。
思路
状态与转移
= 到达石头 的最小代价。到达 的最后一步可以来自任意 :
$$f_i = \min_{j=\max(1,i-K)}^{i-1} \left( f_j + |h_i - h_j| \right).$$直接按这个式子做,每次枚举 个前驱。
为什么不需要更复杂的数据结构
朴素的 已是 ,完全够用。注意不要试图用单调队列优化——代价里带绝对值,最优前驱并不随 单调,斜率优化也不适用(代价不是关于 的二次函数)。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <algorithm> using namespace std; int main() { int n, k; scanf("%d %d", &n, &k); static long long h[100005], f[100005]; for (int i = 1; i <= n; i++) scanf("%lld", &h[i]); f[1] = 0; for (int i = 2; i <= n; i++) { f[i] = (1LL << 60); for (int j = max(1, i - k); j < i; j++) f[i] = min(f[i], f[j] + llabs(h[i] - h[j])); } printf("%lld\n", f[n]); return 0; }易错点
- 下界要写 : 可能 。
- 当 时可以一步从 跳到 ,答案应为 ——用暴力样例可以验证()。
- 初值不要用
0,要设成足够大的数,否则 会被 污染。
数据说明
共 18 组:4 组官方样例;(退化为 Frog 1)、、 极值、 随机; 时取 各一组,另有大小交错的构造组,用于检验转移边界 是否写对。
- 1
信息
- ID
- 11
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者