过河题解

这道题上手一看其实就可以很明确的感觉是DP,据说有人DFS干翻这题，%%%%，我觉得就是dp好理解一点。
首先我们可以很明确的写出这个方程dp[i]=min(dp[i],dp[i+j]+vis[i]);i是当前的位置,j是我要走的步数,vis这个地方是否有石头，这个处理我们是要从后面处理到前面，因为，我们的i+j是往后加的，仔细观察我的dp方程就理解了，然后这样做也是错的，为什么呢，数据范围，看看，1e9，狼心出题人，卡死一个线性处理，离散化，这个有点厉害，这个离散化的思想是，dis=s*t之后的大于这个范围我们都可以在[s,t]这个范围里面找数字去得到，所有我们就可以把大于dis=距离的变成dis，然后是不是就把以前的距离变小然后重新vis一下，这题离散化思想很重要。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int now[maxx];
int ans[maxx];
int dp[maxx];
int main()
{
    fio;
    int n;
    cin>>n;
    int s,t,m;
    cin>>s>>t>>m;
    for(int i=1;i<=m;i++)
        cin>>ans[i];
        int sum=0;
  //  mse(dp,0x3f3f3f);
    if(s==t)
    {
        int an=0;
        for(int i=1;i<=m;i++)
        {
            if(ans[i]%s==0)
                an++;
        }
        cout<<an<<endl;
    }
    else
    {
        sort(ans+1,ans+1+m);
        int dis;
        int pp=s*t;
        for(int i=1;i<=m;i++)
        {
            dis=ans[i]-ans[i-1];
            if(dis>pp)
            {
                dis=pp;
            }
            sum+=dis;
            now[sum]=1;
        }
    for(int i=sum;i>=0;i--){
            dp[i]=0x3f3f3f;
        for(int j=s;j<=t;j++)
    {
        //cout<<dp[i]<<endl;
        dp[i]=min(dp[i],dp[i+j]+now[i]);
    }}
    cout<<dp[0]<<endl;
    }
    return 0;

}