过河

看到L就知道，一定不能开个这么大的数组，且也不能按照这个1e9循环，一定超时；并且m石子数量只有100；所以，就需要用离散化进行化简。也就相当于，距离较远的石子用距离近的点代替；

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
const ll maxn=2000000;
int l,s,t,h,m,discre[maxn],stone[maxn];//discre是离散化之后石子位置的数组，Stone是石子初始位置；
int dp[maxn];//记录到达i时，经过的最小石子数，dp[i]=min(dp[i],dp[i-j]+discre[i])
int main()
{
    cin>>l>>s>>t>>m;
    for(int i=1;i<=m;i++)
    cin>>stone[i];
    sort(stone+1,stone+1+m);//排序
    for(int i=1;i<=m;i++)//离散化，h记录了离散化之后的长度L
    {
        if(stone[i]-stone[i-1]>s*t) h+=(stone[i]-stone[i-1])%t+t*s;
//第i个石子的位置到前一个石子的位置大于t*s，进行离散；
        else h+=stone[i]-stone[i-1];
        discre[h]=1;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=h+t;i++)
    {
        for(int j=s;j<=t;j++)
            if(i>=j) dp[i]=min(dp[i],dp[i-j]+discre[i]);
    }
    int ans=0x3f;
    for(int i=h;i<=h+t;i++) ans=min(ans,dp[i]);
    cout<<ans;
}