【每日一题】5月9日 过河

题意:河宽 ，河中有 个石子，青蛙想要过河，青蛙每次可以跳 的距离,问青蛙过河至少要踩多少块石子。

分析：经典的状态压缩dp.

• 我们先不考虑范围,先将所有石子的位置进行排序， 到第 的位置最少踩的石子数量.转移方程:
  
• 显然空间太大，那么考虑如何优化空间.
  其实很多 是没有意义的,假如 远大于 ,那么对于下标为 到下标为 的dp值 有很多部分并无实际转移价值。考虑压缩dp状态.
• 每次青蛙跳跃的距离是 ,那么 以后的距离是都能到达的，如果两个石子间的距离大于的话，我们将状态压缩为 .那么空间就优化完成了.
• 那么如何得到最终答案.
  我们并不知道终点在哪里，但是我们知道起点的位置。那么我们考虑从逆向dp求解得到答案。

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

typedef long long ll;

const int maxn=2e5+10;


int len,s,t,m,ans;
int a[maxn],b[maxn],dp[maxn];

int main()
{
    cin>>len>>s>>t>>m;
    for( int i=1;i<=m;i++ ) cin>>a[i];
    if( s==t )
    {
        for( int i=1;i<=m;i++ ) 
        {
            if( a[i]%s==0 ) ans++; 
        }
        printf("%d\n",ans);
        return 0;
    }
    sort(a+1,a+1+m);
    int ed=0,base=s*t;
    for( int i=1;i<=m;i++ )
    {
        if( a[i]-a[i-1]>=base ) ed+=base;
        else ed=ed+a[i]-a[i-1];
        b[ed]=1;
    }

    for( int i=ed;i>=0;i-- )
    {
        dp[i]=100;
        for( int j=s;j<=t;j++ ) dp[i]=min(dp[i],dp[i+j]+b[i]);
    }
    printf("%d\n",dp[0]); 
}