[洛谷P1052]过河
/ / 阅读耗时 17 分钟难度：提高+/省选-
题目描述
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0，1，… ，L(其中L是桥的长度)。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S，T)。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S，T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
输入输出格式
输入格式:
第一行有1个正整数L(1≤L≤109)，表示独木桥的长度。
第二行有3个正整数S，T，M分别表示青蛙一次跳跃的最小距离，最大距离及桥上石子的个数，其中1≤S≤T≤10，1≤M≤100。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。
输出格式:
一个整数，表示青蛙过河最少需要踩到的石子数。
输入输出样例
Sample input
10
2 3 5
2 3 5 6 7
Sample output
2
题解
考察线性动态规划，难点在于离散化数据。
令dp(x)表示到达x这个点时踩到的最少的石子数，则状态转移方程为:
这里status(x)在x处没有石子时为0，否则为1。起初dp均置为inf，dp(0)置为0。
答案即为$\max\{dp(L+k)，0 \leq k<T\}$。
但是注意到L非常大，一维数组会直接爆掉，必须采取离散化的方法降低数组大小。这里利用石子数很少的特点压缩。
为了讲清楚压缩的方法，下面先介绍几个概念和原理。
引理：若dp(x)已知，青蛙经过合理的跳跃次序从x跳到y，[x，y]中没有任何石子，则dp(y)=dp(x)。引理显然。
源区间：对于一个石子，假定其坐标是x，那么称区间[x-T，x)为源区间。很容易证明，如果青蛙想要跳过这个石子，一定会经过源区间。这也就是说，倘若源区间中的所有DP值全部求得，那么这个石子所在位置及其后面的所有点的DP值都可以由状态转移方程推出。由此我们得到了一个重要结论。某一石子及其后的所有DP值只与这个石子源区间的值有关。
容易发现，源区间的长度是T。如若两个石子距离本身就不大于T，则我们称这个石子对应的源区间是不完整的。
由上面的结论可以发现，对于拥有完整源区间的一个石子，倘若在其前方的区间段中有一段与源区间同样长的区间且它们的值完全相等，则这两个区间是等价的，此时把石子移动到新的区间的右端点上，不影响结果。由引理可知，只需找到一段区间可以使其中任一点都可以经合理的次序跳到源区间的对应位置上即可。
下面探讨缩点方法。
2520缩：取1，2，… ，10的最小公倍数2520。容易发现，无论S，T为何值，青蛙总可以从x点跳跃至x+2520处的点。也就是说，将石子向前挪动2520个单位(如果可以移动的话)，不影响结果，类似地，将石子后移2520个单位同样不影响结果。这样的操作我们称之为同解变形。
72缩：经过数论上的证明(见题后注解)，可以发现方程:Sx1+(S+1)x2+…+TxT-S+1=72在1 ≤ S < T ≤ 10时一定是有自然数解的。同样可以知道对于任意的S，T(S < T)，青蛙总可以从x跳跃至x+72处。将石子向前向后移动72个单位仍然是同解变形。
当然还有其它缩点方案，但原理都是一致的。
值得注意的是，无论怎么变形，都必须保证两个源区间中没有石子，否则引理条件不满足，无法证明两个区间等价。比如两个石子距离2521而T为5时，不能将后一个石子向前挪2520个单位，这是因为新的源区间包含了前一个石子。72缩同理。
另一个值得注意的是，72缩必须对S=T的情况进行特判。2520缩不需要是因为即使S=T，2520仍然可以整除S，青蛙跳跃2520/S次仍然可以跳跃2520个单位。但72缩时由数论内容，只有S < T时方程有自然数解，当S=T时，也仅有S=1，2，3，4，6，8，9时有解。倘若数据给定S=T=7，那么青蛙不可能跳跃若干步达到72个单位距离。因此S=T时需要特判(实际上只需特判S=T且为5，7，10即可)。
只要跳过最后一个石子迟早能到达桥的末端，直接置L为最后一个石子的位置即可，这样可以从最后一个石子的”后源区间”取答案。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
352520缩：
using namespace std;
int L, S, T, M;
int op[101] = {0}, op2[101] = {0};
int status[258000] = {0};
int dp[258000];
int main() {
cin >> L >> S >> T >> M;
for (int i = 1; i <= M; i++)cin >> op[i];
sort(op + 1, op + M + 1);
for (int i = 1; i <= M; i++) {
if (op[i] - op[i - 1] > 2520) {
op2[i] = (op[i] - op[i - 1]) % 2520 + op2[i - 1];
if (op2[i] - op2[i - 1] <= T)op2[i] += 2520;
} else op2[i] = op2[i - 1] + op[i] - op[i - 1];
status[op2[i]] = 1;
}
L = op2[M];
for (int i = 1; i < L + T; i++)dp[i] = inf;
dp[0] = 0;
for (int i = 0; i < L; i++) {
for (int j = S; j <= T; j++)
dp[i + j] = min(dp[i + j], dp[i] + status[i + j]
);
}
int ans = inf;
for (int i = L; i < L + T; i++)ans = min(ans, dp[i]);
cout << ans;
return 0;
}
1 | 72缩： |
注解
这里给出72缩的数学证明，以下内容涉及初等数论的相关内容，建议读者在熟悉初等数论的基础上阅读。
先介绍一个定理。
[赛瓦维斯特定理]给定两个互素的正整数a，b。若$ax+by=z$没有非负的整数解，则z具有最大值，该值为$ab-a-b$。
证明:
由$(a，b)=1$可知任意整数z，不定线性方程$ax+by=z$都是有解的。容易知道，对于不定方程的一个特解$x_0，y_0$，知$x_0+bt，y_0-at$也是方程的解，也就是说这些解x，y满足：$x \equiv x_0(mod b)，y \equiv y_0(mod a)$，它们本质上是同一组解。
我们证明$ax+by=z$在a，b互素时，仅有这样的一组解。假设x，y满足$ax+by=z$，而$ax_0+by_0=z$，作差得$a(x-x_0)+b(y-y_0)=0$，故有$ax \equiv ax_0(mod b)$。由于$(a，b)=1$，所以$ax \equiv ax_0(mod b)$就是$x \equiv x_0(mod b)$。故仅有一组解。
(扩展:$ax\equiv b(mod m)$在$(a，m)|b$时有解，且有$(a，m)$组解)
对于这样的一系列解，必存在这样的一个解$x_1$，$y_1$满足$-b\leq x_1<0$且$y_1>0$。
这个时候若$x_1$加上$b$，就一定可以使x对应的解非负，但同时$y_1$要减去$a$。倘若$y_1 \geq a$，则对应的$ax+by=z$必然是有非负整数解的。倘若$y_1 < a$，容易知道此时无论$x_1$加上多少倍的$b$，都不能使x和y同时非负，这时方程是无解的。
由此，我们得到方程无解等价于$-b\leq x_1<0$时有$y_1<a$。
在这个基础上令x1，y1分别取它们的最大值-1，a-1，代入原方程得到:
这就是无解的z的最大值。证毕。
由这个定理，我们就可以更好地理解72缩的原理。
容易知道相邻的两个自然数是互素的，那么这两个自然数a，a+1不能线性表示的最大数是a*(a+1)-a-a-1=a2-a-1。给定S和T(S