题解 | #过河#

如果不考虑L的范围，就是一道简单的dp题。f[i]表示走到位置i，踩到的石头个数的最小值，则f[i]=min(f[i], f[j] + flag[i])，其中flag[i]表示位置i是否是石子，j在[i-s, i-t]之间。

当L很大时，但是石子个数很少最多只有100个，所以存在两个石子之间有很大的空隙。

下面分两种情况来讨论：

1. 当s==t：走法唯一，每次跳的距离为s，统计在位置满足是s的整数倍的上的石子的个数
2. 当s!=t： 我们考虑不能被s, s+1, s+2, ..., T 所表示的数有哪些。结论：如果我们只用两个相邻的数p， q，那么不能被表示的数的最大值是(p-1)(q-1)-1，因此所有大于等于(p-1)(q-1)-1的数一定可以被p，q表示出来。

当p=9，q=10时取到最大值，此时(p-1)(q-1)-1=72，因此所有大于72的数，一定可以被s, s+1, s+2, ..., T 表示出来。所以将每个距离前一个石子距离超过100的石子都可以往左压缩，将线段的长度缩短为100，得到的结果是等价的。此时最多只会用到100*100=10000个位置，复杂度可以通过了

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200000;
int stones[110];
int f[N], flag[N];
int main() {
    int L;
    scanf("%d",&L);
    int s,t,m;
    scanf("%d %d %d", &s,&t,&m);

    for(int i = 1; i <= m; i++){
        scanf("%d", &stones[i]);
    }
    sort(stones, stones+m+1);
    //当 s=t，每次跳只能跳固定的距离，所以统计 跳到的石子总和就是答案
    if(s==t){
        int sums = 0;
        for(int i = 1; i<=m;i++){
            if(stones[i]%s==0)
                sums ++;
        }
        printf("%d", sums);
        return 0;
    }

    //将 石子点往左压缩
    for(int i = 1, last = 0, offset = 0; i<=m;i++){
        //当 前后两个石子距离大于100，就将后面的石子往左移动一个offset，移动之后对结果无影响，因为距离太大，超过了一步能移动的最大距离。
        if(stones[i]-last>=100){
            offset += stones[i]-last-100;
        }
        last = stones[i];
        stones[i] -= offset;
    }
    //标记石子位置
    for(int i = 1; i <= m; i++){
        flag[stones[i]] = 1;
    }
    //动态规划求解答案
    //遍历所有可以跳到的位置，不是遍历 每个石子
    L = stones[m]+10;  // 最远跳到最后一个石子的右边最多10就可以了。不需要跳到或跳过终点，只要跳过了最后一个石头，那跳到最后，石子的数量也不会变多了。
    for(int i = 1; i <= L; i++){
        f[i] = 110;  //最满足的情况的最大值，最多100个石子
        for(int j = s; j<=t;j++)
        {
            if (i-j>=0)
                f[i] = min(f[i], f[i-j]+flag[i]); 
        }
    }
    printf("%d",f[L]);

    return 0;
}
// 64 位输出请用 printf("%lld")