洛谷P1052过河题解--zhengjun
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0,1,…,L0,1,…,L0,1,…,L（其中LLL是桥的长度）。坐标为000的点表示桥的起点，坐标为LLL的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是SSS到TTT之间的任意正整数（包括S,TS,TS,T）。当青蛙跳到或跳过坐标为LLL的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度LLL，青蛙跳跃的距离范围S,TS,TS,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
输入格式第一行有111个正整数L(1≤L≤109)L(1 \le L \le 10^9)L(1≤L≤109)，表示独木桥的长度。
第二行有333个正整数S,T,MS,T,MS,T,M，分别表示青蛙一次跳跃的最小距离，最大距离及桥上石子的个数，其中1≤S≤T≤101 \le S \le T \le 101≤S≤T≤10,1≤M≤1001 \le M \le 1001≤M≤100。
第三行有MMM个不同的正整数分别表示这MMM个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
输出格式一个整数，表示青蛙过河最少需要踩到的石子数。
输入输出样例 输入 #1 复制10
2 3 5
2 3 5 6 7
输出 #1 复制
2
说明/提示
对于30%30\%30%的数据，L≤10000L \le 10000L≤10000；
对于全部的数据，L≤109L \le 10^9L≤109。
200520052005提高组第二题
思路一看到题目，喂耶！这么水的dpdpdp还可以搞成蓝色标签。
用fif_ifi表示跳到第iii个石头后最少要踩到多少块石头。
马上就列出了转移公式：
fi=min(∞,min{fi−j,s≤j≤t})f_i=\min(\infty,\min\{f_{i-j},s\leq j\leq t\})fi=min(∞,min{fi−j,s≤j≤t})
这里的∞\infty∞是为了防止j<sj<sj<s的情况。
可是乍眼一看。
L≤109L≤10^9L≤109
什么鬼东西，数组搞个10910^9109内存早炸了。
于是，发现aia_iai的值很大，而aaa的个数十分小，所以——离散化
那么，怎么个离散化法呢？
因为aia_iai的值很大，所以两两之间的空隙十分多，我们就可以在这里做文章。
因为如果两个aaa之间有一段长度，是lcm(s,t)lcm(s,t)lcm(s,t)(((就是sss和ttt的最小公倍数)))，这样的话，从左端点，无论是走sss还是ttt，他都可以走到右端点(实际上就是剩下一些多余的没有跳到石头上的路)，这样我们就要把这一段切掉。
但是还要考虑一个问题，如果切掉之后长度小于lcm(s,t)lcm(s,t)lcm(s,t)，那么就会影响答案了，就比如说：
s=1,t=2s=1,t=2s=1,t=2
原来是：
|***|*|***|
1 2 3 4--最优解
| | | |
. # . . # .
^ ^
石头 石头
而被你一缩，成了
|***|*|
1 2 3
| | |
. . . .
^ ^
石头
就要踩到一个石头了。（实际上会错202020分）
所以，为了保证答案的正确性，就要这么办：
如果之间的距离小于2×lcm(s,t)2\times lcm(s,t)2×lcm(s,t)，那么就不用变。 如果大于它，就要缩点（注意，不能缩到lcm(s,t)lcm(s,t)lcm(s,t)，要缩到lcm(s,t)lcm(s,t)lcm(s,t)到lcm(s,t)×2−1lcm(s,t)\times2-1lcm(s,t)×2−1之间才可以）最后，我们来想一想数组要开多大。
因为缩点之后，两点的距离不会超过lcm(s,t)×2lcm(s,t)\times2lcm(s,t)×2，所以缩完点后最大就是lcm(s,t)×2−1lcm(s,t)\times2-1lcm(s,t)×2−1，而lcm(s,t)lcm(s,t)lcm(s,t)最大是909090，所以两点之间最多有179179179。
然后，有100100100个点，就要179×99=17721179\times99=17721179×99=17721。
所以，数组开200002000020000足够了。
最后，还有一个细(kēng)节(diǎn)，会让你丢掉202020分——特判s=ts=ts=t
代码#include
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
int l;
int s,t,m;
int a[101],b[101];
int f[20000];
int flag[20000];
int gcd(const int &x,const int &y){//求最大公约数
if(y==0)return x;
return gcd(y,x%y);
}
int lcm(const int &x,const int &y){//求最小公倍数
return x*y/gcd(x,y);
}
int main(){
scanf("%d%d%d%d",&l,&s,&t,&m);
int k=lcm(s,t);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
if(s==t){//特判
int sum=0;
for(int i=1;i<=m;i++)if(a[i]%s==0)sum++;
printf("%d",sum);
return 0;
}
a[m+1]=l;//最后一个终点也算上去
sort(a+1,a+1+m);
for(int i=1;i=2*k)b[i]=(a[i]-a[i-1])%k+k;//缩点
else b[i]=a[i]-a[i-1];
}
for(int i=1;i<=m+1;i++){
a[i]=a[i-1]+b[i];
flag[a[i]]=1;
}
flag[a[m+1]]=0;//终点不会有石头
for(int i=1;i<=a[m+1]+t+1;i++){//这里用了一个不存在的状态来表示最终答案——跳出终点或跳到终点
f[i]=0x3fffffff;//初始化
for(int j=s;j<=min(i,t);j++){
f[i]=min(f[i],f[i-j]+flag[i]);//公式
}
}
printf("%d",f[a[m+1]+t+1]);//输出
return 0;
}
谢谢–zhengjun
作者：A_zjzj
