[NOIP2005 提高组] 过河（C++，DP，数据压缩）

题目描述

在河上有一座独木桥一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点$0,1,\cdots ,L$其中 $L$ 是桥的长度。坐标为 $0$ 的点表示桥的起点坐标为 $L$ 的点表示桥的终点。青蛙从桥的起点开始不停的向终点方向跳跃。一次跳跃的距离是 $S$ 到 $T$ 之间的任意正整数包括 $S,T$。当青蛙跳到或跳过坐标为 $L$ 的点时就算青蛙已经跳出了独木桥。

题目给出独木桥的长度 $L$青蛙跳跃的距离范围 $S,T$桥上石子的位置。你的任务是确定青蛙要想过河最少需要踩到的石子数。

输入格式

输入共三行

• 第一行有 $1$ 个正整数 $L$表示独木桥的长度。
• 第二行有 $3$ 个正整数 $S,T,M$分别表示青蛙一次跳跃的最小距离最大距离及桥上石子的个数。
• 第三行有 $M$ 个不同的正整数分别表示这 $M$ 个石子在数轴上的位置数据保证桥的起点和终点处没有石子。所有相邻的整数之间用一个空格隔开。

输出格式

一个整数表示青蛙过河最少需要踩到的石子数。

样例 #1

样例输入 #1

10
2 3 5
2 3 5 6 7

样例输出 #1

2

提示

【数据范围】

• 对于 $30\%$ 的数据$1\le L\le 10^4$
• 对于 $100\%$ 的数据$1\le L\le 10^9$$1\le S\le T\le 10$$1\le M\le 100$。

【题目来源】

NOIP 2005 提高组第二题

解题思路

把每次跳跃看作一次选择那么每次选择一共有$T-S+1$种可能

最简单的方法就是暴力搜索尝试每一种可能选出其中最小值时间复杂度是指数级的显然会超时

搜索可以采用记忆的方式来优化但在这里我们略过这种优化方式转而去尝试是否能进行动态规划

动态规划最重要的自然是状态转移方程

ans[i] = min(ans[i], ans[i - j] + stones[i])

其中i为青蛙当前位置如果青蛙站在石头上stones[i]为true反之则为falseS <= j <= T

本题直到这里仍属于一道普通的动态规划问题然后我们看一下数据范围max_L = 1e9

显然这么大的数据是没办法存进数组里的所以我们需要将其压缩

如图所示其中$s=2,t=3$$s_i$~$t_i$为第$i$次跳跃的范围

可知在第$3$次跳跃之后之后的每一个点都是可以到达的

而$3$次跳跃的距离就是$s$与$t$的最小公倍数lcm(s, t)

若两个石头间的距离大于lcm(s, t)我们可以把它们的距离压缩为lcm(s, t)

原因是ans[i]在lcm(s, t)之后、下一个石头之前均相同可以自行验证一下

最后AC代码如下

//动态规划 + 数据压缩
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int max_m = 100;
const int max_s = 10;
const int max_t = 10;
const int max_l = 100 * max_s * max_t;
const int NaN = 0x3F3F3F3F;

bool new_stones[max_l + 1];
int stones[max_m];
int dp[max_l + 1];
int L, S, T, M, ans;

int main() {
	int stone;
	cin >> L >> S >> T >> M;
	for (int i = 0; i < M; i++) cin >> stones[i];
	if (S == T) {//S == T 特判
		ans = 0;
		for (int i = 0; i < M; i++)
			if (stones[i] % S == 0)
				ans++;
	}
	else {
		//数据压缩
		sort(stones, stones + M);
		int stone1 = 0, stone2, t = stone1, dist, lcm = S * T;
		for (int i = 0; i < M; stone1 = stone2, i++) {
			stone2 = stones[i];
			dist = stone2 - stone1;
			t += min(lcm, dist);
			new_stones[t] = true;
		}

		memset(dp + 1, 0x3F, sizeof(int) * (t + lcm));
		for (int i = S; i <= t + lcm; i++) {
			for (int j = S; j <= min(i, T); j++) {
				dp[i] = min(dp[i], dp[i - j] + new_stones[i]);
			}
		}
		ans = NaN;
		for (int i = t + 1; i <= t + lcm; i++) {
			ans = min(ans, dp[i]);
		}
	}
	cout << ans;
	return 0;
}