P1052 [NOIP2005 提高组] 过河

这个dp挺好想的，每次走的位置是知道的，所以走到那个点，就能知道从那个点过来的。
然后再分到的这个点是不是石头，如果是石头就总数加一，否则就不变。

难得地方是范围的问题。l最大能到一亿，这样的话，就要缩短距离，缩短的话，就离散化。
我们只需将每两个石头超过 s×t 的距离缩成s×t就可以了。
算是了解了离散化的概念

#include

using namespace std;
const int maxn = 150;
const int maxl = 300 * 105;
//其实开90 * 105就可以了；
int L,s,t,m,ss[maxn],a[maxn],dp[maxl],base;
//stone就是石头的初始位置；a为我们将石头初始化后的石头位置；
bool v[maxl];
//标记一下坐标上的该点是否为石头；
int main()
{
    int l,s,t,m;
    cin>>l>>s>>t>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>ss[i];
    }
    sort(ss+1,ss+1+m);
    int b=s*t;
    if(s==t)
    {
        int c=0;
        for(int i=1;i<=m;i++)
        {
         if(ss[i]%s==0)
            c++;
        }
         cout<=b)
            t=b;
            a[i]=a[i-1]+t;
            v[a[i]]=1;
    }
    l=a[m]+b;
        memset(dp,0x7f,sizeof(dp));
        dp[0]=0;
        for(int i=1;i<=l;i++)
        {
            for(int j=s;j<=t;j++)
            {
                if(i-j>=0)
                {
                        if(v[i])
                    {
                        dp[i]=min(dp[i],dp[i-j]+1);

                    }
                    else
                    dp[i]=min(dp[i],dp[i-j]);

                }
            }
        }
        int minn=9999999;
        for(int i=a[m];i<=l;i++)
        {
            minn=min(minn,dp[i]);
        }
        cout<