P1052 过河
斯德哥尔摩
2018-10-14 11:43:54
[P1052 过河](https://www.luogu.org/problemnew/show/P1052)
首先，题目有个大坑：
### 青蛙不是一定要跳到石头上！
### 而是青蛙尽量不踩石头的情况下还要跳到多少个石头上！
这个活坑啊。。。
然后这个题很显然是个$DP$。。。
设$dp[i]$表示从$0$到$i(\text{横坐标})$最少踩了多少石子。
很容易得出一个和背包很像的转移方程：
$$dp[i]=\min\{dp[i-j]+stone[i]|j\in[s,t]\}$$
这里的$stone[i]$表示$i$这个位置是否有石子。
$BUT$！这个$i$有个巨大的范围：$10^9$
这$^{TM}$是要爆炸的节奏啊。。。
于是想优化。
我们知道我们要优化的就是坐标对吧。。。
所以**路径压缩**横空出世！
当然并不是并查集。。。
目的是要找到两块石子相隔距离较长时直接缩短的方法。
下面盗了一份某位大佬的证明（[链接](https://www.luogu.org/blog/littlejuruo/solution-p1052)）：
假设每次走$p$或者$p+1$步，我们有$\gcd(p,p+1)=1$。
由扩展欧几里得可知，对于一个二元一次方程：
$$px+(p+1)y=\gcd(p,p+1)$$
是有整数解的。
即：$px+(p+1)y=s$是一定有整数解的。
设$px+(p+1)y=s$的解为：
$$\left\{\begin{array}{rcl}x&=&x_0+(p+1)t\\y&=&y_0-pt\end{array}\right.$$
令$x\in[0,p]\text{(可以通过增减t个p+1来实现)},s>p\times(p+1)-1$
则有：
$$y=\frac{s-px}{p+1}>=\frac{s-p^2}{p+1}>\frac{p(p+1)-1-px}{p+1}>=0$$
即：
当$s>=p(p+1)$时，方程$px+(p+1)y=s$有两个非负整数解，每次走$p$步或者$p+1$步，$p(p+1)$之后的地方均能够到达。
所以如果两个石子之间的距离大于$p(p+1)$，那么就可以直接将他们之间的距离更改为$p(p+1)$。
这样，我们便得到了压缩路径的方法：
若$\text{两个石子之间的距离}>t(t-1)$，则将他们的距离更改为$t(t-1)$。
因为$t<=10$，因此我们可以直接将大于$10\times9$的距离直接化为$90$。
当然我的程序中为了好看直接设成$100$了。
但是注意，对于$s==t$这种特殊情况，这种方法是不成立的！
因为在这种情况下，每次是不能够走$p+1$步的，因此需要另外解法。
这种情况的转移方程长这样:
$$f[i]=f[i-1]+(i \mod s ==0)$$
然后就没有然后了。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 110
#define MAX 999999999
using namespace std;
int n,m,s,t,ans=MAX;
int pos[MAXN],stone[MAXN*MAXN],dp[MAXN*MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
if(s==t){//特判
ans=0;
for(int i=1;i<=m;i++)ans+=(pos[i]%s==0);
printf("%d\n",ans);
return;
}
dp[0]=0;
for(int i=1;i<=n+9;i++){
dp[i]=MAX;
for(int j=s;j<=t;j++)if(i>=j)dp[i]=min(dp[i],dp[i-j]+stone[i]);
}
for(int i=n;i<=n+9;i++)ans=min(ans,dp[i]);
printf("%d\n",ans);
}
void init(){
n=read();s=read();t=read();m=read();
for(int i=1;i<=m;i++)pos[i]=read();
sort(pos+1,pos+m+1);
pos[0]=0;pos[m+1]=n;
n=0;
for(int i=1;i<=m+1;i++){
n+=min(pos[i]-pos[i-1],100);
stone[n]=1;
}
}
int main(){
init();
work();
return 0;
}
```