【每日一题】过河

Question：

青蛙从桥头跳过独木桥，跳过就行，桥长为 ，青蛙跳过的路程 只要大于等于 就行。桥上有一些石头，题目会给石头的数量m和m个石头的位置，还有青蛙跳跃的最小距离s、最大距离t。

Analysis：

离散化+dp。
这个离散化和我学过的不一样，我之前学的离散化是把一个大的集合向一个小的集合映射，而这题的离散化是省去不必要的距离，缩小区间。
如果 那么很简单，只有一条路径，没得选择，统计踩到多少石头就行， 表示会踩到这个石头， 是石头的位置。
就要考虑离散化了：(p和t只是为了证明，和题目无关)
1.假设每次走或 步。
2. ，也就是和 一定是互质的。
3.可以知道 有整数解，也可得 也是一定有解的。
4.设3的解为： 。
5.最后可以得到当 时， 有两个非负整数解，具体原理可以去看看扩展欧几里得解的情况。
6.根据5可以知道每次走或 步， 步及其之后的地方都可以走到，所以接下来就可以愉快的离散化了。
7.这里 看成是题目输入的 ，也就是说如果两点之间的距离大于 都可以直接缩小为。
8.具体一点就是把 个石头和起点、终点看成 个点，他们之间的距离和就是离散化后桥的长度，因为离散化后桥的长度最大为 ，也就是9000，所以可以用数组stone标记离散化后石头的位置。第一个石头的位置是它和起点离散化后的距离，第二个石头的位置是它和第一个石头离散化后的距离加上前面一个石头的位置，其它的石头的位置也是这么算的。
9.因为可以跳出独木桥，所以答案要在 之间找， 是离散化后桥的长度，为什么不是 呢，因为到了终点就不用再跳了。
10.因为 小于等于90，所以写代码时我都是用90代替它。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int dis[105],a[105],stone[maxn],f[maxn],p;//局部变量的值都是0 
int main() {
    int l,s,t,m;
    read(l);
    read(s),read(t),read(m);
    if(s==t) {
        int pos,cnt=0;
        for(int i=1;i<=m;++i){
            read(pos);
            cnt+=(pos%s==0);
        }
        printf("%d\n",cnt);
        return 0;
    }
    for(int i=1;i<=m;++i)    read(a[i]);
    sort(a+1,a+1+m);
    for(int i=1;i<=m;++i) {
        dis[i]=min(a[i]-a[i-1],90);//a[0]等于0，也就是起点 
        p+=dis[i];
        stone[p]=1;
    }
    dis[m+1]=min(l-a[m],90);
    p+=dis[m+1];
    for(int i=1;i<=p+9;++i) {
        f[i]=0x3f3f3f3f;
        for(int j=s;j<=t;++j) if(i>=j)
        f[i]=min(f[i],f[i-j]+stone[i]);
    }
    int ans=0x3f3f3f3f;
    for(int i=p;i<=p+9;++i) ans=min(ans,f[i]);
    printf("%d\n",ans);
}