题解 | #过河#

#include <bits/stdc++.h>
using namespace std;

//此题解参考了 https://www.nowcoder.com/users/133865280 这位大佬的题解，尝试把他的思路解释得更加清晰

//若按照一般思路的dp，直接设开一个大小为L + 1的dp数组，其中dp[i]表示青蛙到达第i的位置时需要踩到的最小石头数量
//则设dp的全部数据初始化为inf,然后令dp[0] = 0，因为第i个位置只能由前[S,T]个位置跳达，因此状态转移方程为
//dp[i] = min(dp[i], dp[i-j] + hasStone? 0 : 1), j ∈ [S,T]
//这样会爆内存或者超时，主要原因是L 高达 10的9次方

//优化的思路，注意到L有10^9，而石头最多只有100个，也就是说每两个石子之间的距离可以长达10^7！ 而中间这么多点都
//是没有石子的，因此不会对最终结果产生影响，就可以直接省略掉！对于两个石子之间距离特别大的情况（距离起码大于
//T）举例说明如下：
// i ...T+i ...2T+i ...3T+i ...... nT+i  j
// 设某两个石子的位置为i 和 j， 那么从i出发青蛙肯定能够达到的点为 kT+i (k=1...n)，其中 j>= nT+i，其实根据
//状态转移方程不难发现，区间的值dp[kT+i+1, (k+1)T+i]和上一个区间dp[(k-1)T+i+1,kT+i]的值是一样的，也就是出现了重复
//和循环，因此只需要把n个长度为T的重复区间给优化剩下1个即可，这个可以通过取(j - i) mod T + T实现，注意这里最少要有一个T的长度，因为在这种情况下 ij之间的距离是大于T的

//i ... j .. T
//考虑另外一种情况，即i和j之间的距离小于等于T，则i和j之间的点都有可能跳到j，因此这些点得全部考虑，不能压缩

int main() {
    int L;
    int S, T, M;
    cin >> L >> S >> T >> M;
    vector<int> stones;
  //考虑出发点
    stones.push_back(0);
    int a;
    for(int i = 0; i < M; i ++){
        cin >> a;
        stones.push_back(a);
    }
  //考虑中点
    stones.push_back(L);
    sort(stones.begin(), stones.end());
    
    //cout << endl;
    //计算新的stone位置
    set<int> hasStone;
    //这是计算出来的新的桥的长度
    int l = 0;
    for(int i = 1; i < stones.size(); i ++){
        auto dis = stones[i] - stones[i - 1];
        //如果两个石子中间的距离小于T，则之间的点位都得考虑
        if(dis <= T){
            l += dis;
        //如果两个石子中间的距离大于T，则中间有很多段T的距离是不用考虑的可以直接mod T，只用考虑最后一段T到2T的距离
        }else{
            l += dis % T + T;
        }
        //记录新的石头位置, 首尾两端0 和 L的位置没有石头
        if(i > 0 && i < stones.size() - 1)
            hasStone.insert(l);
    }

    //因为青蛙最后可能会越过l，跳到l + T的后面，还要加上最后一段T
    int NL = l + T;

    //定义dp数组
    vector<int> dp(NL + 10, 100000);
    dp[0] = 0;
    for(int i = 1; i <= NL; i++){
        for(int j = S; j <= T; j ++){
            if(i >= j){
                dp[i] = min(dp[i], hasStone.count(i-j) == 0? dp[i-j] : dp[i-j] + 1);
            }
        }
    }
    auto ans = 100000;
    for(int i = l; i <= NL; i ++){
        ans = min(ans, dp[i]);
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")