题意

• 给定桥的长度L，每一步可以走S~T中任意距离，桥上共有M颗石子，求走过桥最少踩多少石子
• 0<= L <=1e9, 1<=S<=T<=10, 1<=M<=100

思路

• 一个类似于走楼梯的动态规划，很显然的可以得到转移方程:其中，S<=j<=T，0<=i<=L
• 但是，由于L的范围很大，不可能开下这么大的dp数组，所以需要对长度进行压缩
• 参考NOIP2017|小凯的疑惑，数字a，b不能表示的最大数是
• 因为最大步长为10，所以所有超过71的数都可以等价的压缩成72
• 完成路径压缩后即可正常处理，对于L由于不要求恰好过桥，所以i的范围可以变为1<=i<=压缩后的最后一个石头+1

AC代码

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

int a[200],b[200],vis[20202];
int dp[20202];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int L,S,T,M;
    memset(dp,0x3f3f3f3f,sizeof(dp));

    cin >> L >> S >> T >> M ;
    if(S==T){
        int ans=0;
        for(int i=1;i<=M;i++){
            cin >> a[i] ;
            if(a[i]%S==0) ans++;
        }
        cout << ans << '\n';
        return 0;
    }
    for(int i=1;i<=M;i++){
        cin >> a[i] ;
    }
    sort(a+1,a+1+M);

    //路径压缩
    for(int i=1;i<=M;i++){
        if(a[i]-a[i-1]>72){
            b[i]=b[i-1]+72;
        }else{
            b[i]=b[i-1]+(a[i]-a[i-1]);
        }
    }
    
    for(int i=1;i<=M;i++) vis[b[i]]=1;
    // for(int i=1;i<=M;i++) cout << b[i] << ' ' ;
    
    b[M+1]=b[M]+1;
    dp[0]=0;
    // cout << b[M+1] << '\n';
    for(int i=1;i<=b[M+1];i++){
        for(int j=S;j<=T;j++){
            if(i<j) continue;
            // cout << i << ' ' << j << '\n';
            dp[i]=min(dp[i],dp[i-j]+vis[i]);
        }
    }
    cout << dp[b[M+1]] << '\n' ;
    return 0;
    
}