【学习笔记】路径压缩dp
NCC79601
2019-06-18 13:35:19
## 例题 [P1052](https://www.luogu.org/problemnew/show/P1052)
瞟一眼一下这道题，感觉好像是个很简单的$\text{dp}$，只需要用$f[i]$维护在$i$位置需要踩的最少石子数，然后按照$f[i]=\min(f[i-j]\vert i-j\geq0,j\in[s,t])+stone[i]$转移一发即可。
但是仔细一看：$N\leq\text{1e9}$，完蛋。
转移方法肯定是不会改变的，那么肯定需要用某种方式进行离散化（也就是所谓的**路径压缩**），然后再进行转移。
# 分析
观察这道题的$s,t\in[1,10]$，然后一想：$lcm(1,2,\cdots,10)=2520$，然后$2520\times100=252000=\text{2e5}$，这好像就变成正常数据范围了。
事实上这是**正确的**。这里使用的路径压缩就是用$lcm(1,2,\cdots,10)=2520$来对每一段距离取模，从而达到缩短路径的目的。可以简单思考一下， 不管青蛙怎么样跳，它肯定可以跳到$2520$处，合情推理一下，对$2520$取模之后的距离可以表示原距离的**所有情况**，也就是说是不是一定会踩到石头上只与对$2520$取模之后的余数相关，而与多出去的那一部分无关。这个也不难理解，总可以用某种距离组合来得出压缩之前的情况。
因此，可以大胆地进行**路径压缩**！具体方式为找到一种能将长距离状态简化为短距离状态的方法，此后再进行$\text{dp}$。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int LCM = 2520;
const int MAXN = 110;
int l, s, t, m;
int a[MAXN], d[MAXN], f[MAXN * LCM];
bool stone[MAXN * LCM];
int main()
{
scanf("%d%d%d%d", &l, &s, &t, &m);
for(int i = 1; i <= m; i++)
scanf("%d", &a[i]);
sort(a + 1, a + m + 1);
for(int i = 1; i <= m; i++)
d[i] = (a[i] - a[i - 1]) % LCM;
for(int i = 1; i <= m; i++)
{
a[i] = a[i - 1] + d[i];
stone[a[i]] = true;
}
l = a[m];
// descrete
// printf("%d\n", l);
for(int i = 1; i <= l + t; i++)
f[i] = m;
f[0] = 0;
for(int i = 1; i <= l + t; i++)
for(int j = s; j <= t; j++)
{
if(i - j >= 0)
f[i] = min(f[i], f[i - j]);
f[i] += stone[i];
}
int ans = 0x3f3f3f3f;
// printf("%d", ans);
for(int i = l; i < l + t; i++)
ans = min(ans, f[i]);
printf("%d", ans);
return 0;
}
```