1 条题解
-
1
[A] Frog 1(dp_a)题解
题意简述
一排 块石头,高度 。青蛙从 出发,每次可跳 或 格,落到石头 的代价为 ,求到达 的最小总代价。
思路
状态与转移
唯一需要知道的信息是"现在站在哪块石头上",于是设 为从石头 跳到石头 的最小总代价。到达 只能从 或 跳来:
$$f_i = \min\left(f_{i-1} + |h_i - h_{i-1}|,\; f_{i-2} + |h_i - h_{i-2}|\right)\quad (i \ge 3).$$答案是 。
为什么正确
任何一条到达 的路径,其最后一步必然从 或 出发;而到达 (或 )的最优代价与之后怎么跳无关(无后效性)。因此把两种情况的"最优前驱"都试一遍取最小即可。
复杂度
时间 ,空间 (可优化到 )。
参考代码
#include <cstdio> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); static long long h[100005], f[100005]; for (int i = 1; i <= n; i++) scanf("%lld", &h[i]); f[1] = 0; f[2] = llabs(h[2] - h[1]); for (int i = 3; i <= n; i++) f[i] = min(f[i - 1] + llabs(h[i] - h[i - 1]), f[i - 2] + llabs(h[i] - h[i - 2])); printf("%lld\n", f[n]); return 0; }易错点
- 是题目保证的,但仍建议对 特判(不跳,代价 ),否则
f[2]越界。 - 的值最大约 ,int 勉强够用,但习惯上开
long long更安全。 - 初始化 时别把 写成 ——题目只计算跳跃的代价,起点高度不计入。
数据说明
共 16 组:前 3 组为官方样例;另有 的两个极值( 与反向)、全等高(答案 )、单调递增/递减、大小交错、 随机、 的随机/全同/递增/全 等,用于卡住"只跳 1 格"与"只跳 2 格"的错误贪心。
- 是题目保证的,但仍建议对 特判(不跳,代价 ),否则
- 1
信息
- ID
- 10
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者