https://www.luogu.org/problemnew/show/P1052
题目描述
在河上有一座长度为 L 的独木桥, 一只青蛙想沿着独木桥从河的一侧跳到另一侧. 在桥上有一些石子, 青蛙很讨厌踩在这些石子上. 由于桥的长度和青蛙一次跳过的距离都是正整数, 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点: 0, 1, ..., L. 坐标为 0 的点表示桥的起点, 坐标为 L 的点表示桥的终点. 青蛙从桥的起点开始, 不停地向终点方向跳跃, 一次跳跃的距离是 [S, T] 上的正整数. 当青蛙跳到或跳过坐标为 L 的点时, 就算青蛙已经跳出了独木桥.
题目给出独木桥的长度 L, 青蛙跳跃距离的最小值 S, 最大值 T, 和桥上石子的位置. 你的任务是确定青蛙想要过河, 至少会踩到多少石子.
输入输出格式
输入格式:
第一行有一个正整数 L ( 1 ≤ L ≤ 10), 表示独木桥的长度.
第二行有三个正整数 S, T, M, 分别表示青蛙一次跳跃的最小距离, 最大距离以及桥上石子的个数, 其中 1 ≤ S ≤ T ≤ 10, M ≤ 100.
第三行有 M 个互不相同的正整数, 表示 M 个石子在独木桥上的位置. 数据保证桥的起点和终点处没有石子. 所有相邻的整数间用一个空格分隔.
输出格式:
一个整数, 表示青蛙想要过河最少需要踩到的石子数.
输入输出样例
输入样例:
10
2 3 5
2 3 5 6 7
输出样例:
2
解题思路
状态转移方程
设 f[i] 为走到 i 处所需踩的最少的石子数. 显然, 有 f[i] = min(f[i - j]) + flag[i] ( S ≤ j ≤ T ).
路径压缩
由 2017d1t1 可知, 任何与当前位置距离不小于 S * T 的点都是可以到达的, 所以第一个石头到起点的距离, 两个相邻石头之间的距离和最后一个石头到终点的距离如果大于 S * T, 就可以压缩到 S * T. 这样, 我们就可以把 10的数据压缩到 10 以内.
注意: 这个方法对于 S == T 的情况不适用, 需要进行特判.
实现
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define IsDigit(x) ((x) >= '0' && (x) <= '9')
using namespace std;
int l, s, t, m;
], road[], dp[], q[][];
int Read(void)
{
);
c = getchar();
while (!IsDigit(c))
c = getchar();
do
ret = ret * + c - ';
while ((c = getchar()) && IsDigit(c));
return ret;
}
int main()
{
), ), rr(-);
l = Read();
s = Read();
t = Read();
m = Read();
; i <= m; ++i)
in[i] = Read();
sort(, );
if (s == t) {
ans = ;
; i <= m; ++i)
&& ++ans;
printf("%d\n", ans);
;
}
);
; i <= m; ++i) {
in[i] -= mark;
] > base) {
mark += ] - base;
] + base;
}
road[in[i]] = true;
}
l = min(in[m] + base, l);
memset(dp, , sizeof(dp));
dp[] = ;
for (int i = s; i < l + t; ++i) {
])
--rr;
q[++rr][] = dp[i - s];
q[rr][] = i - s;
i - q[ll][] > t && ++ll;
dp[i] = q[ll][] + road[i];
}
ans = ;
for (int i = l; i < l + t; ++i)
ans = min(dp[i], ans);
printf("%d\n", ans);
;
}感谢我的数学老师