过河

Question

Analysis

这题如果数据范围再小一点的话很明显可以用dp求解，大概就是这样：

bool vis[maxn];//位置i有无石子
int dp[maxn];//到达位置i的最小踩石子数
    fill(dp,dp+maxn,INF);//全部初始化为最大
    dp[0] = 0;
for(int i = 1 ; i <= L ; ++i){
    for(int j = s ; j <= t ; ++j ){
            if(i >= j) dp[i] = min(dp[i],dp[i-j]+vis[i]);
    }
}

但是L的范围是1e9，直接算会爆内存的，所以就想到了离散化.
通过观察法，如果青蛙位置是X，那如果X+S到X+T位置都有石头那青蛙才可能踩到石头，
所以那些间隔很远的石头完全可以缩短距离，至于缩短多少距离呢,这个时候就灵机一动 偷看大佬的题解 ,就把距离大于 S * T 的石头缩短为 S * T，至于为什么。打个草稿就好了。
如果 S = 5 ，T = 6：

• 走一步 能走 5 ~ 6 个单位

• 走两步 能走 10 ~ 12 个单位

• 走三步 能走 15 ~ 18 个单位

• 走四步 能走 20 ~ 24 个单位

• 走五步 能走 25 ~ 30 个单位

• 走六步 能走 30 ~ 36 个单位

• 走七步 能走 35 ~ 42 个单位
  举例发现距离大于等于 30 单位的位置都可以到达，然后找一下规律（大佬一眼看出）多列几个就发现距离大于S * T的位置都能到达。所以把距离大于 S * T 的石头缩短为 S * T就好

  因为青蛙可能跳出桥，所以最后的答案要求 缩短距离后的最大位置 + S*T 之间的最小值

吐槽 ： 石头的位置居然不是有序的，我在这看了好久能a的代码，最后还是看ac代码才发现要排序

Code

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 1e5+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll ston[105],b[105];//b[i]是离散化后的石头位置
bool vis[95*100];
ll dp[95*100];
int main(){
    ll l = read();
    int s = read(),t = read(),m = read();
    for(int i = 1 ; i <= m ;++i){
        ston[i] = read();
    }
    if(s == t){
        ll ans = 0;
        for(int i = 1 ; i <= m ;++i) 
            if(ston[i]%s == 0) ++ans;
            cout<<ans<<endl;
            return 0;
    }
    sort(ston+1,ston+1+m);
    int div = s*t;
    for(int i = 1 ; i <= m ; ++i){
        int tmp = ston[i]-ston[i-1];
        if(tmp>div) tmp = div;//距离大于s*t的改成s*t
        b[i] = b[i-1]+tmp;
        vis[b[i]] = true;
    }
    for(int i = 1 ; i <= b[m]+div; ++i) dp[i] = 1e18; 
    for(int i = 1 ; i <= b[m]+div ; i++){
        for(int j = s ; j <= t ; ++j){
            if(i >= j){
              if(vis[i])  dp[i] = min(dp[i],dp[i-j]+1);
              else dp[i] = min(dp[i],dp[i-j]);
            }
        }
    }
    ll ans = 1e18;
    for(int i = b[m] ; i < b[m]+div ; i ++){
        ans = min(dp[i],ans);
    }
    cout<<ans<<endl;
}