/*
经典状态压缩dp
其实也不是很难只是被知识点名字吓到了
连循环数组优化都不用加就直接AC了
首先我们可以知道的是，这道题的问题在于L太大了，不可能开一个这么大的数组来存放所有的点
估计就是ORZ然后爆炸了然后运行都运行不了23333
但是这题的突破口在于：
1.首先不多说，特判，如果s==t，那么就只能s，s地跳，这个就是个简单的情况了，直接特判。
计算出能经历多少个这样的点在s的整数倍坐标上即可
排除此情况后：
2.石子的数量实在是太小了，最多100个QAQ，试想一个10^9的数轴上，只有一百个有效点，
剩下的都是空点,而其中很多的空点其实是没有实际意义的
所以我们就压缩一下咯,首先排序,对于排好序的石头数(注意：石子并没有按顺序给出要排序)
我们可以观察两个相邻的石头，
中间那一块空地是不管怎么样都不会影响到下一块石头的数量的(你乱蹦乱跳怎么弄也都是空地)
那么我们就把中间这块空地给压缩一下吧
我们考虑一下，对于一片空地而言，至少要多长的空地才能让青蛙对这些地方处处可达？
ORZ我数学其实不好，所以引用一下Peeeeeach的题解中的话吧
{
讲一下这个题的数学分析思路吧。首先桥很长，但石子很少，所以可以对桥的长度进行压缩，
然后再DP。首先特判S==T，如果相等的话，那么就看石子是否落在S的整数倍格子上。
然后我们再进行分析。青蛙最坏的情况就是S=T-1，它每次跳跃只有两种选择，我们只考虑这种情况即可。
问题的关键就是多么长的空地才能保证青蛙对这些空地是处处可达的？假设这个距离是X，
那么比X长的空地也都是处处可达的，就与长为X的空地等效了，因此这就是压缩长度的关键。
最后的结论是X=T^2。青蛙跳跃X需要跳T次T长度，但是可以把每个T逐个换成S（也就是T-1）
那么TS到TT就是跳T次能到达的所有格子了。而跳T-1次能到达的最大长度为(T-1)T=ST，
与跳T次的最小长度衔接上了。而T的最大值是10，也就是X取100。
因此先对输入数据进行一次初始化，如果发现两个石子之间的长度比100大，那么就直接视为它们相距100即可。
}
不多说先膜拜%%%%Peeeeeach大神
Px+(P+1)y=Q

x,y是未知数，P是跳跃的距离，P+1也是跳跃的距离，对于任意Q，Q>=P*(P-1),
x，y一定存在正整数解，换句话说当两个石子之间的距离大于等于T*(T-1)时，
中间有相当大的距离是每个点都可以跳到的，因为没有石子，所以对答案没有贡献，可以取模(%90),
这样就很好办了。。。于是我们就成功地把状态给压缩了。
那么处理好这个问题以后我们就可以进行压缩了，对于每两个相邻石头距离一言不合就直接%个100吧，
但是弱比的我发现这里的数据%90也可以，可能是没有这种T==10&&S=T-1的极端数据吧
3.注意最后的结果一定要算到l+t(因为跳出范围也是合法的)，最终输出答案时，
在f[L]到f[L+t]中找到最优解输出
其他不多说了，直接看代码吧
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1100000;
const int MAXM=105;
const int MOD=90;
int stone[MAXM];
int a[MAXN];
int f[MAXN];
int L,s,t;
int n;

void init()
{
    scanf("%d%d%d%d",&L,&s,&t,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&stone[i]);
}

void solve()
{
    int tot=0;
    for(int i=1;i<=n;i++)
        if(stone[i]%s==0)
            tot++;
    cout<<tot<<endl;
    exit(0);
}

void work()//处理石头~缩掉里面的空地
{
    sort(stone+1,stone+n+1);
    for(int i=1;i<=n;i++)
    {
        int dist=stone[i]-stone[i-1];
        stone[i]=stone[i-1]+dist%MOD;
    }
    L=(L-stone[n])%MOD+stone[n];
    for(int i=1;i<=n;i++)
        a[stone[i]]=1;
}

void DP()
{
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=s;i<=L+t;i++)//第一次至少也会跳到s
        for(int j=s;j<=t;j++)
            if(i>=j)
                f[i]=min(f[i],f[i-j]+a[i]);
    int ans=(1<<30)-1;
    for(int i=L;i<=L+t;i++)
        ans=min(ans,f[i]);
    cout<<ans<<endl;
}

int main()
{
    init();
    if(s==t)//特判s==t
        solve();
    work();
    DP();
}
   

讲一下这个题的数学分析思路吧。首先桥很长，但石子很少，所以可以对桥的长度进行压缩，然后再DP。首先特判S==T，如果相等的话，那么就看石子是否落在S的整数倍格子上。然后我们再进行分析。青蛙最坏的情况就是S=T-1，它每次跳跃只有两种选择，我们只考虑这种情况即可。问题的关键就是多么长的空地才能保证青蛙对这些空地是处处可达的？假设这个距离是X，那么比X长的空地也都是处处可达的，就与长为X的空地等效了，因此这就是压缩长度的关键。
最后的结论是X=T^2。青蛙跳跃X需要跳T次T长度，但是可以把每个T逐个换成S（也就是T-1）那么T*S到T*T就是跳T次能到达的所有格子了。而跳T-1次能到达的最大长度为(T-1)*T=S*T，与跳T次的最小长度衔接上了。而T的最大值是10，也就是X取100。
因此先对输入数据进行一次初始化，如果发现两个石子之间的长度比100大，那么就直接视为它们相距100即可。

好气哇,因为没看清石头是无序的，各种wa,终于排序就过了。

时隔2年，突然想起当年没过的这题，翻出来，基本思路就清楚了，石头排个序直接AC了，诶，不细心的毛病看来还一直保留着。

讲讲这题的题解吧。

首先将问题简化，先看30%的情况。

我们可以很简单的发现，这题的状态是很好设计的，把数轴上每个点都看成一个一维状态就好了，能到达这个状态的前置状态只有该状态的左边S-T个状态（想想递归的话要如何实现？）

然后只要正着递推30%就过了。

到这里，**实际上动态规划的内容我们都已经做完了，因为状态，状态转移方程都设计好了。**

那么先处理L过长的问题，因为L过长，因此我们开不出这么大的状态数组，我们看之前的分析，我们都知道一个状态最多由其前S-T个数组递推而得到，因此我们最大只需要开T个大小的数组即可，即10个，然后滚动数组即可，也就是说我们用到的状态不超过20个。

然后由于L过大，O（n）的效率显然不太合适，由于算法O（n）已经很优秀了，我们要做的只能减少N的范围，我们发现，石头的数量实在太少了，少的不合理，因此实际上，有太多太多的状态是没必要的。想象一样，在一段完全没有石头的状态内跳来跳去答案根本不会有所变化，真正会产生影响的应该是有石头的附近。

因此当我们检测到我们的滚动dp数组连续2次答案没有变化时，就可以知道，我们正在一个空档内跳，这个时候我们要快进掉这个无用的过程，直接将当前位置瞬移到下一块石头前T块即可。

一下代码可以参考

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <ctype.h>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l+r)>>1)
#define fst first
#define snd second
using namespace std;
typedef long long lint;

const int MAXN = 11;


int dp[MAXN],last[MAXN];
int stone[110];
int l,s,t,m;
map<int,bool> num;

bool hasChange(){
    for(int i = 1; i <= t; ++i){
        if(dp[i] != last[i]){
            return true;
        }
    }
    return false;
}

bool cmp(int a,int b){
    return a < b;
}

int main(){
    scanf("%d",&l);
    scanf("%d%d%d",&s,&t,&m);
    num.clear();
    stone[0] = 0;
    for(int i = 1; i <= m; ++i){
        scanf("%d",&stone[i]);
        num[stone[i]] = true;
    }
    stone[++m] = l;
    sort(stone+1,stone+1+m,cmp);
    memset(last,0x7f,sizeof(last));
    last[t] = 0;

    lint st = 0;
    int now = 0;
    while(st < l){
        memset(dp,0x7f,sizeof(dp));
        for(int i = 1; i <= t; ++i){
            for(int j = s; j <= t; ++j){   //滚动数组
                if(num[st + i] != 0){
                    if(i - j <= 0){
                        dp[i] = min(dp[i],last[t-(j-i)] + 1);
                    }else{
                        dp[i] = min(dp[i],dp[i-j] + 1);
                    }
                }else{
                    if(i - j <= 0){
                        dp[i] = min(dp[i],last[t-(j-i)]);
                    }else{
                        dp[i] = min(dp[i],dp[i-j]);
                    }
                }
            }
        }

        st += t;
        if(st >= l){
            break;
        }

        while(st >= stone[now+1]){
            ++now;
        }

        if(!hasChange()){   //这个IF是快进的关键部分，去掉只过30%数据
            st = ((stone[now+1] - 1) / t) * t;
        }

        for(int i = 1; i <= t; ++i){
            last[i] = dp[i];
        }
    }

    int ans = 9999999;
    for(int i = t-(st-l); i <= t; ++i){
        ans = min(ans,dp[i]);
    }

    printf("%d\n",ans);
    return 0;
}

#include <cstdio>
#include <algorithm>
#include <cstring>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Dor(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define M 100
#define L 2520//lcm(1-10)
using namespace std;

//核心：dp+路径压缩 
int l,s,t,m,a[M+1],stone[M*L+1],f[M*L+1];
int main(){
    scanf("%d%d%d%d",&l,&s,&t,&m);
    For(i,1,m) scanf("%d",&a[i]);
    sort(a+1,a+m+1);
    For(i,1,m){
        a[i]=a[i-1]+(a[i]-a[i-1])%L;//将路径压缩 
        stone[a[i]]=1;
    }//接下来直接dp即可 
    memset(f,127,sizeof(f));
    f[0]=0;
    For(i,s,M*L){
        For(j,s,t){
            if (i>=j) f[i]=min(f[i],f[i-j]+stone[i]);
        }
    }
    printf("%d\n",f[M*L]);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int l,s,t,m;
int f[900000];
int pos[200];
int a[900000];
int main()
{
scanf("%d%d%d%d",&l,&s,&t,&m);//依次读入桥的长度，最小跳跃距离，最大跳跃距离，桥上石子个数
for(int i=1;i<=m;i++)
scanf("%d",&pos[i]);//表示石子在桥上的数轴位置
sort(pos+1,pos+m+1);//这个石子的分布位置 Maybe是无序的，所以还是来个排序
if(s==t) //如果这只青蛙跳跃的距离为一定值
{
//slove();
int ans=0;
for(int i=1;i<=m;i++)
if(pos[i]%s==0) ans=ans+1; //要是下落点正好在 M 个石子中的某一个，则 Ans 累加
printf("%d",ans);
return 0; //直接结束程序
}
for(int i=1;i<=m;i++) //接下来就是对相邻石子间距的压缩
{
int temp=pos[i]-pos[i-1]; //相邻两个石子间的距离之差
pos[i]=pos[i-1]+temp%90; //因为间距太大，对答案没有贡献 所以就直接压缩不必要的距离 可以在这把距离 %90
}
l=pos[m]+(l-pos[m])%90; //最后第 M 枚石子到终点的距离压缩
for(int i=1;i<=m;i++)
a[pos[i]]=1; //将每个石子的权值都赋值为 1

memset(f,127,sizeof(f));
f[0]=0; //状态初始化
for(int i=1;i<=l;i=i+1) //DP
for(int j=s;j<=t;j=j+1)
if(i-j>=0)
f[i]=min(f[i-j]+a[i],f[i]); //f[i] 表示走过 i 米，所踩到的最少石子数
printf("%d",f[l]);
}
/*注意
1 题中所给的石子的数轴位置为无序的数据
2 题中的桥很长，而石子却很少
3 每两个相邻的石子的距离可能会 大于等于100 ——那么就直接视为它们相距100 （状态压缩吧）
4 还有要特判 S==T 那么就看石子是否落在S的整数倍数轴点上
*/

#include<iostream>
#include<algorithm>
using namespace std;
int l,s,t,m,ans;
int f[11000]={0},a[110];
int st[11000]={0};
void ys()
{
int k=110,x;
for(int i=1;i<=m+1;i++)
{
x=a[i]-a[i-1];
if(x>k)
a[i]=a[i-1]+(a[i]-a[i-1])%k;
st[a[i]]=1;
}
st[a[m+1]]=0;
f[0]=0;
for(int i=1;i<=a[m+1]+t-1;i++)
{
f[i]=105;
for(int j=s;j<=t;j++)
if(i>=j) f[i]=min(f[i],f[i-j]);
f[i]+=st[i];
}
ans=101;
for(int i=a[m+1];i<=a[m+1]+t-1;i++)
ans=min(ans,f[i]);
cout<<ans<<endl;
}
int main()
{
cin>>l>>s>>t>>m;
ans=0;
a[0]=0;
a[m+1]=l;
for(int i=1;i<=m;i++)
cin>>a[i];
sort(a+1,a+m+1);
if(s==t)
{
for(int i=1;i<=m;i++)
if(a[i]%s==0)
ans++;
cout<<ans<<endl;
}
else ys();
return 0;
}

{
解题思路

copy

此题显然要用到DP，DP方程也显而易见：
if (stone[i]) f[i]=min{f[i-j]}+1; (S<=j<=T)
else f[i]=min{f[i-j]};
这样的时间复杂度为 O(LT) ，空间复杂度为 O(L) 。{
而此题的L高达 10亿 ，所以这种朴素的方法只能得 30分 ，显然无法AC。
优化

1.滚动数组
根据我们得出的DP方程，状态转移只需用到 f[i-T]~f[i-S] 的值，所以只需开大小为T的滚动数组即可。
所以空间复杂度被优化到了 O(T) 。由于T小于等于10，所以空间上显然没有问题。
2.离散化DP
看了看别人的题解，发现有人选择压105位来优化，这种方法虽然能过，但是或多或少有投机取巧的嫌疑，毕竟比赛时谁知道去压正好105位呢？
所以我们必须想出一般性的方法。我们会发现，石头的个数M远远小于长度L，不禁让我们想到了离散化——当S<T且有一大段桥没有石头时，常常会出现整个滚动数组f的值一样的情况，这时我们可以在遇到下一颗石头之前不再改变f的值，从而达到优化的效果。
在下用tot变量记录当前数值连续出现的次数，如果超过T次，则将i直接跳转到下一个石头的位置之前，从而提高效率。
优化后，时间复杂度降至 O(MT) ，已经达到了AC的要求。
特判

上面的离散化显然建立在S<T的基础上。如果S==T，那么永远达不到优化的条件，优化就不会奏效，从而 *TLE：90分 * 。
因此我们必须加上特判，当S==T时，ans就是位置为T的倍数的石头的数量。

首先，石头是需要排序的，没话说，我第一次就错在这上面（当然DP也不对）。
再者，关键是状态的压缩，因为当两个石头的距离过长的时候，青蛙大部分时间都用来蹦跳白地。即因为两石之间差距太大，青蛙不管跳S还是跳T都在白地上跳。作为与小动物和谐共处的我们自然不能看小小青蛙受到如此虐待，我们只去关注在靠近石子不远的地方青蛙的活动就可以了。所以把距离mod某个数以缩剪掉白地部分。这个某个数我不会证明怎么来取，我只知道mod100的话会RP的AC。
{这里一个实现技巧，把Stone[0]:=0;Stone[M+1(一)]:=BridgeLong，到时候把Stone[M+1(一)]再赋回BridgeLong可以同时缩减BridgeLong}
最后就是一些细节问题了，比如从0~S之间的点是无论任何也跳不到的（除非它在跳的途中做了次垂直落体运动），所以DP从S开始。而且最后需要从BridgeLong到BridgeLong+T中找最优解，因为题目允许跳过去。

最后后，总而言之，这其实是一道很简单的DP，不要被状态压缩的名头吓到。它与其它DP题目最大的区别在于代码长了不少。

算法流程

}

var
l,s,t,n,m,i,j,ans:longint;
a:array[0..110]of longint;
f:array[0..100000]of longint;
flag:array[0..100000]of boolean;

procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l; j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

function min(x,y:longint):longint;
begin
if x<y then exit(x) else
exit(y);
end;

begin
readln(l);
readln(s,t,m);
for i:=1 to m do read(a[i]);
if s=t then
begin
for i:=1 to m do

if a[i] mod s=0 then inc(ans);
writeln(ans);
end else
begin
sort(1,m);
for i:=1 to m do
begin
if a[i]-a[i-1]>90 then
begin
for j:=i to m do
a[j]:=a[j]-((a[i]-a[i-1]) div 90)*90;
l:=l-a[i] div 90;
end;
end;
for i:=1 to m do flag[a[i]]:=true;
if l-a[m]>90 then l:=l-((l-a[m]) div 90)*90;
for i:=1 to l+t do
begin
f[i]:=maxlongint>>2;
for j:=s to t do
if i-j>=0 then
if flag[i] then f[i]:=min(f[i],f[i-j]+1) else
f[i]:=min(f[i],f[i-j]);
end;
ans:=maxlongint;
for i:=l to l+t do ans:=min(ans,f[i]);
writeln(ans);
end;
end.

// .. Orz ..

var l,kk,s,t,m,i,j,temp,max:longint;
a:array[0..1000]of longint;
b,f:array[0..1000000]of longint;
begin
readln(l);
read(s,t,m);
for i:=1 to m do
read(a[i]);
kk:=0;
if s=t then
begin
for i:=1 to m do
if a[i] mod s =0 then inc(kk);
write(kk);
halt;
end;
for i:=1 to m-1 do
for j:=i+1 to m do
if a[i]>a[j] then begin temp:=a[i];a[i]:=a[j];a[j]:=temp;end;
for i:=1 to m do
if a[i]-a[i-1]>100 then
begin
kk:=a[i]-a[i-1]-100;
for j:=i to m do
a[j]:=a[j]-kk;
end;
fillchar(b,sizeof(b),0);
for i:=1 to m do
b[a[i]]:=1;
l:=a[m];
for i:=1 to l+t do f[i]:=100;
f[0]:=0;
for i:= s to l+t do
for j:= s to t do
if (i-j>=0)and (f[i-j]+b[i]<f[i]) then f[i]:=f[i-j]+b[i];
max:=100;
for i:= l to l+t do
if f[i]<max then max:=f[i];
write(max);
READLN;READLN
end.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1100000;
const int MAXM=105;
const int MOD=90;
int stone[MAXM];
int a[MAXN];
int f[MAXN];
int L,s,t;
int n;

void init()
{
scanf("%d%d%d%d",&L,&s,&t,&n);
for(int i=1;i<=n;i++)
scanf("%d",&stone[i]);
}

void solve()
{
int tot=0;
for(int i=1;i<=n;i++)
if(stone[i]%s==0)
tot++;
cout<<tot<<endl;
exit(0);
}

void work()//处理石头~缩掉里面的空地
{
sort(stone+1,stone+n+1);
for(int i=1;i<=n;i++)
{
int dist=stone[i]-stone[i-1];
stone[i]=stone[i-1]+dist%MOD;
}
L=(L-stone[n])%MOD+stone[n];
for(int i=1;i<=n;i++)
a[stone[i]]=1;
}

void DP()
{
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=s;i<=L+t;i++)//第一次至少也会跳到s
for(int j=s;j<=t;j++)
if(i>=j)
f[i]=min(f[i],f[i-j]+a[i]);
int ans=(1<<30)-1;
for(int i=L;i<=L+t;i++)
ans=min(ans,f[i]);
cout<<ans<<endl;
}

int main()
{
init();
if(s==t)//特判s==t
solve();
work();
DP();
}
请勿粘贴

step 1理解题意
在做这道题之前，一定要理解好题意，有一个需要特别注意注意的地方：

青蛙不是一定要跳到石头上[嗯...这一点坑了我好久]而是指青蛙尽量不踩石头的情况下还要跳到多少个石头上[语文渣求原谅]。

step 2状态转移方程
这是一个比较简单方程式。

首先设f[i]为在i点上的最少踩石子数则在前面(i-s)到(i-t)的点都可以改变i点的值,因此我们可以取f[i-s]-f[i-t]之中的最小值，另外如果有石头就加上1，如果没有就不加值，这里我们直接用flag[i]表示该点有无石头(有则为1，无则为0)。

因此我们可以写出状态转移方程式:f[i]=\min(f[i-j]+flag[i]|s<=j<=t)f[i]=min(f[i−j]+flag[i]∣s<=j<=t)
step 3路径压缩
实际上，这题还没完呢...如果我们定义一个f[10^9]的数组，这肯定是会爆内存的——所以...[我就放弃了这道题][额，可能吗]..因此我们需要使用一种方法，使得这里采用一种最合适的方法——路径压缩(其实还有其他更(bu)优(kao)秀(pu)方法的)，目的是要找到两石同相隔较长时直接缩短的方法。[前方高能,请数学学科恐惧症患者尽快撤离!!]:

假设每次走p或者p+1步.我们知道\gcd(p,p+1)gcd(p,p+1)=1.

由扩展欧几里得可知，对于二元一次方程组：

px+(p+1)y=\gcd(p,p+1)px+(p+1)y=gcd(p,p+1)是有整数解的，即可得：px+(p+1)y=spx+(p+1)y=s是一定有整数解的。

设px+(p+1)y=spx+(p+1)y=s的解为：x=x0+(p+1)t,y=y0-ptx=x0+(p+1)t,y=y0−pt。令0<=x<=p0<=x<=p(通过增减t个p+1来实现)，s>p*(p+1)-1s>p∗(p+1)−1,

则有：y=\frac{s-px}{p+1}>=\frac{s-p^2}{p+1}>\frac{p*(p+1)-1-px}{p+1}>=0y=
p+1
s−px
​ >=
p+1
s−p
2

​ >
p+1
p∗(p+1)−1−px
​ >=0
即表示，当 s>=p*(p+1)s>=p∗(p+1) 时，px+(p+1)y=spx+(p+1)y=s 有两个非负整数解，每次走p步或者 p+1p+1 步，p*(p+1)p∗(p+1) 之后的地方均能够到达。

如果两个石子之间的距离大于 p*(p+1)p∗(p+1) ，那么就可以直接将他们之间的距离更改为 p*(p+1)p∗(p+1) 。

综上，得到压缩路径的方法：若两个石子之间的距离> t*(t-1)t∗(t−1) ，则将他们的距离更改为 t*(t-1)t∗(t−1) 。

因为 t<=10t<=10 ，因此我们可以直接将大于10*9的距离直接化为90.

但是要注意，对于 s=ts=t 这种特殊情况，这种方法是不成立的应为在这种情况下，每次是不能够走p+1步的，因此需要另外特殊判断。

方程如下:

f[i]=f[i-1]+(i \mod s ==0)f[i]=f[i−1]+(imods==0)

#include<iostream> 
#include<cstdio> 
#include<algorithm> 
#include<climits> 
using namespace std; 
int f[10005],far[10005],a[10005],flag[10005],p,s,t,n; 
int main() 
{ 
    scanf("%d",&p); 
    scanf("%d%d%d",&s,&t,&n); 
    if(s==t) //特殊情况判断
    { 
        int cont=0,qaq; 
        for(int i=1;i<=n;++i)scanf("%d",&qaq),cont+=((qaq%s)==0); 
        printf("%d\n",cont);return 0; 
    } 
    for(int i=1;i<=n;i++)scanf("%d",&a[i]); 
    sort(a+1,a+n+1);a[0]=0;f[0]=0; 
    far[n+1]=min(p-a[n],100);p=0; //计算终点与最后一个点的距离
    for(int i=1;i<=n;i++)far[i]=min(a[i]-a[i-1],90),p+=far[i],flag[p]=1; //缩短路径，存储缩短后的终点距离并标记石头位置
    p+=far[n+1]; 
    for(int i=1;i<=p+9;i++) 
    { 
        f[i]=INT_MAX-1; 
        for(int j=s;j<=t;j++)if(i>=j)f[i]=min(f[i],f[i-j]+flag[i]); 
    } 
    int minn=INT_MAX-1; 
    for(int i=p;i<=p+9;i++) //因为青蛙可以跳出边界且t<=10因此再终点后p-p+9中取最小值
    minn=min(minn,f[i]); 
    printf("%d",minn); 
} 

给一个java版本

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt();
        int s = scanner.nextInt();
        int t = scanner.nextInt();
        int m = scanner.nextInt();
        int[] ms = new int[m + 1];
        for (int i = 0; i < m; i++) ms[i] = scanner.nextInt();
        if (s == t) {
            int v = 0;
            for (int i = 0; i < m; i++) if (ms[i] % t == 0) v++;
            System.out.println(v);
            return;
        }
        ms[m] = l;
        Arrays.sort(ms);
        int n = 0;
        int[] vs = new int[t];
        int[] vb = new int[t];
        int count = 0;
        int y = 0;
        for (int i = s; i < t; i++) vb[i] = i;
        vb[0] = t;
        for (int i = s, k = s; i < l; i++, k++) {
            if (k == t) k = 0;
            if (vb[k] > 0) {
                if (n < m && i == ms[n]) {
                    vs[k]++;
                    n++;
                }
                for (int j = s; j <= t; j++) {
                    int x = k + j;
                    if (x >= t) x -= t;
                    if (vb[x] != i + j || vs[x] > vs[k]) {
                        vb[x] = i + j;
                        vs[x] = vs[k];
                    }
                }
                if (vs[k] == y) count++;
                else count = 0;
                if (count == t) {
                    i = ms[n] - t;
                    k = i % t;
                    count = 0;
                }
                y = vs[k];
            } else y = -1;
        }
        int v = m;
        for (int i = 0; i < t; i++) {
            if (vb[i] > 0 && vs[i] < v) v = vs[i];
        }
        System.out.println(v);
    }
}

我真的需要补习补习DP了，第一次递交还漏了特判s == t......
状态压缩dp，参考@powderHan

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXM = 105, MOD = 100, MAXN = 1100000;
int l, s, t, m, stone[MAXM], f[MAXM * MAXM], ans = (1 << 30) - 1;
bool h4sh[MAXN];

inline void solve()
{
    int tot = 0;
    for(int i = 1; i <= m; i++) if(stone[i] % s == 0) tot++;
    cout << tot << endl;
    exit(0);
}

int main(){
    cin.sync_with_stdio(false); cout.sync_with_stdio(false);
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; i++) cin >> stone[i];
    sort(stone + 1, stone + m + 1);
    if (s == t) solve();
    for (int i = 1; i <= m; i++){ stone[i] = stone[i - 1] + (stone[i] - stone[i - 1]) % MOD; h4sh[stone[i]] = 1; }
    l = (l - stone[m]) % MOD + stone[m];
    memset(f, 0x3f, sizeof f); f[0] = 0;
    for (int i = s; i <= l + t; i++){
        for (int j = s; j <= t && i >= j; j++){
            f[i] = min(f[i], f[i - j] + h4sh[i]);
        }
    }
    for (int i = l; i <= l + t; i++) { ans = min(ans, f[i]); }
    cout << ans << endl;
}

#include <stdio.h>
struct student{
char name[80],g,x;
int q,b,l,jiang;
}a[120],max;

int main()
{
int n,i,k=0;
char block;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s %d %d %c %c %d",a[i].name,&a[i].q,&a[i].b,&a[i].g,&a[i].x,&a[i].l);
a[i].jiang=0;
if(a[i].q>80&&a[i].l>0)a[i].jiang+=8000;
if(a[i].q>85&&a[i].b>80)a[i].jiang+=4000;
if(a[i].q>90)a[i].jiang+=2000;
if(a[i].q>85&&a[i].x=='Y')a[i].jiang+=1000;
if(a[i].b>80&&a[i].g=='Y')a[i].jiang+=850;
k+=a[i].jiang;
}
max=a[0];
for(i=1;i<n;i++){
if(max.jiang<a[i].jiang)max=a[i];
}
printf("%s\n%d\n%d",max.name,max.jiang,k);
return 0;
}

学会去判断并压缩冗余的区间，
以p(p-1)为界限分类讨论，
以S,T大小关系处理特殊情况.

CODE：
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define mem(a,b) memset(a,b,sizeof(a))
#define differ rock[i]-rock[i-1]
using namespace std;int L,S,T,m,rock[105],f[20010],a[20010],ans=102;
int main(){
    scanf("%d%d%d%d",&L,&S,&T,&m);go(i,1,m)scanf("%d",&rock[i]);    
    if(S==T){ans=0;go(i,1,m)if(!(rock[i]%S))ans++;goto end;}   
    sort(rock+1,rock+m+1);mem(f,0x3f);f[0]=rock[0]=0;
    go(i,1,m){if(differ>=90)rock[i]=rock[i-1]+(differ)%90;a[rock[i]]++;}
    go(i,S,rock[m]+T)go(j,S,T)if(i>=j)f[i]=min(f[i],f[i-j]+a[i]);else break;
    go(i,rock[m],rock[m]+T)ans=min(ans,f[i]);end:printf("%d\n",ans);return 0;
}//Paul_Guderian

\(\rule{10000000mm}{100000000mm}\)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 90 * 105;


int s[maxn],a[maxn];
int dp[maxn],len;

bool f[maxn]; //标记改点是否为石头 
memset(dp,0x7f,sizeof(dp));
int main()
{
    int L,s,t,m;
    cin >> L >> s >> t >> m;
    len = s * t;
    for(int i = 1 ; i <= m ; ++ i)cin >> s[i];
        
    sort(s + 1,s + 1 + m);
    
    if(s == t)//当s与t重复时 
    {
        int sum =0;
        for(int i = 1 ; i <= m ; ++ i)
            if(s[i] % s == 0)sum++;
            
        printf("%d",sum);
        return 0;
    }
    for(int i = 1 ; i <= m ; ++ i)
    {
        int d = s[i] - s[i - 1];//两个石头之间的距离 
        
        if(d >= len)d = len;//过大的距离进行更新 
        
        a[i] = a[i - 1] + d;//将新的石头之间的距离更新到数组a中 
        
        f[a[i]] = 1;//更新新的石头 
        
        if(i==m)L = a[m] + len;//根据最后一个石头来重新更新独木桥的长度 
    }
 
    dp[0] = 0;
    
    for(int i = 1 ; i <= L ; ++ i)
        for(int j = s ; j <= t ; ++ j)
        {
            if(i >= j)
            {
                if(f[i])dp[i] = min(dp[i - j] + 1,dp[i]);
                else dp[i] = min(dp[i - j],dp[i]);
            }
        }
        
    int ans = 200;
    for(int i = a[m] ; i <= L ; ++ i)
        ans = min(ans,dp[i]);
    cout << ans << endl;
    return 0;
}

//（过河）思路：动态规划，动规方程，数组为石子数1或0取min
// 状态压缩，缩小数据，除数取Tmax和Tmax-1的最小公倍数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int YS=90;
const int MAXN=100000;//下方有优化，只开100000，不然需要10000000，内存从44降到1M
int LL[MAXN],s[MAXN],d=101;
int stone[101];
long ll,S,T,y,n;
int main(int argc, char** argv)
{
cin>>ll>>S>>T>>n;
for(int i=1;i<=n;i++)
{
cin>>stone[i];
}
if(S==T)
{
d=0;
for(int ii=1;ii<=n;ii++)
{
if(stone[ii]%S==0) d++;
}
cout<<d;
return 0;
}
else{
sort(stone+1,stone+1+n);
stone[1]=stone[1]%YS;//优化
for(int j=1;j<n;j++)
{
y=stone[j+1]-stone[j];
stone[j+1]=stone[j]+y%YS;
}
ll=(ll-stone[n])%YS+stone[n];
for(int o=1;o<=n;o++)
{
s[stone[o]]=1;
}
memset(LL,0x7f,sizeof(LL));
LL[0]=0;
for(int k=S;k<=ll+T;k++)
{
for(int l=S;l<=T;l++)
{
if(k>=l) LL[k]=min(LL[k],LL[k-l]+s[k]);
}
}
for(int p=ll;p<=ll+T;p++)
{
d=min(d,LL[p]);
}
cout<<d;
return 0;}
}

首先dp方程式
i表示桥上的位置，j表示跳的步数，最小s，最大t

dp[i] = 2100000000 //Init
dp[i] = min(dp[i], dp[i-j]), s<=j<=t

桥的长度是1,000,000,000，但是石子总数才100个，很显然，两个石子间的距离很大，没必要从0扫到10e9。

利用一个性质，即多步距离组合后，在一定距离外可跳至任意一点。因为步数1-10，那么这个距离最大（最坏情况）是10*9-10-9=71，那么每个石子前后区间取大于71，即可保证 该区间最后一个点的值 就是 经过这个区间后踩到最少石子数 。下一个区间前t个值即可拷贝上一个区间的最后一个值。

但是这个算法有例外，就是 s==t 时， 不存在 一定距离外可跳至任意点的性质，因此要写一段例外的处理代码： 直接计算石子位置中有多少个整除s即可 。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXS 105
#define SECLEN 100
#define INF 2100000000
using namespace std;

int secbegin[MAXS], secend[MAXS], secsize = 0;
int sect[MAXS][21000];

int main(){
  int l, s, t, m, st[MAXS], tmin = INF;
  cin >> l >> s >> t >> m;
  for(int i=0; i<m; i++){
    cin >> st[i];
  }
  sort(st, st+m);
    // 例外处理
  if(s == t){
    tmin = 0;
    for(int i=0; i<m; i++){
      if(st[i] % s == 0){
        tmin ++;
      }
    }
    cout << tmin;
    return 0;
  }
    // 计算区间数目 
  for(int i=0; i<m; i++){
    if(i == 0){
      secsize++;
      secbegin[secsize] = max(0, st[i]-SECLEN);
      secend[secsize] = min(l+t, st[i]+SECLEN);
    }else{
      if(st[i] - st[i-1] > SECLEN*2){
        secsize++;
        secbegin[secsize] = max(0, st[i]-SECLEN);
        secend[secsize] = min(l+t, st[i]+SECLEN);
      }else{
        secend[secsize] = min(l+t, st[i]+SECLEN);
      }
    }
  }
    
    // 遍历所有区间
  for(int sid=1; sid<=secsize; sid++){
    for(int i=0; i<=secend[sid] - secbegin[sid]; i++){
      sect[sid][i] = INF;
      if(i < t){
        if(sid == 1){
          sect[sid][0] = 0;
        }else{
          sect[sid][0] = sect[sid-1][secend[sid-1]-secbegin[sid-1]-i];
        }
      }
      for(int j=s; j<=t; j++){
        if(i-j >= 0){
          sect[sid][i] = min(sect[sid][i], sect[sid][i-j]);
        }
      }
      if(binary_search(st, st+m, i+secbegin[sid])){
        sect[sid][i] += 1;
      }
      if(i + secbegin[sid] >= l){
        tmin = min(tmin, sect[sid][i]);
      }
    }
  }
  if(tmin == INF){
    tmin = sect[secsize][secend[secsize] - secbegin[secsize]];
  }
                     
  cout << tmin;
  return 0;
}

评测情况

 Accepted
#   状态  耗时  内存占用
#1  Accepted    3ms     348.0 KiB
#2  Accepted    3ms     256.0 KiB
#3  Accepted    3ms     348.0 KiB
#4  Accepted    5ms     8.352 MiB
#5  Accepted    7ms     4.5 MiB
#6  Accepted    5ms     4.375 MiB
#7  Accepted    6ms     4.496 MiB
#8  Accepted    6ms     4.375 MiB
#9  Accepted    6ms     6.336 MiB
#10     Accepted    3ms     360.0 KiB

#1 Accepted 3ms 428.0 KiB
#2 Accepted 2ms 444.0 KiB
#3 Accepted 2ms 312.0 KiB
#4 Accepted 62ms 444.0 KiB
#5 Accepted 44ms 436.0 KiB
#6 Wrong Answer 26ms 456.0 KiB
#7 Accepted 67ms 440.0 KiB
#8 Accepted 94ms 436.0 KiB
#9 Accepted 71ms 448.0 KiB
#10 Accepted 3ms 312.0 KiB
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define rep0(i,n) for(int i=0;i<n;i++)
#define ll long long
int f[20008],l,s,t,m;
int w[108];
int main(){
cin>>l>>s>>t>>m;
rep(i,m)cin>>w[i];
w[0]=0;
w[m+1]=l;
if(s==t){
int q=0;
rep(i,m)if(w[i]%s==0)q++;
cout<<q<<endl;
return 0;
}
sort(w,w+m+2);
int now=1;
memset(f,120,sizeof(f));
f[0]=0;
rep(i,l){
bool flag=0;
if(i==w[now]){
flag=1;
now++;
}
for(int j=s;j<=t;j++){
if(j>i)break;
f[i%20000]=min(f[i%20000],f[(i-j)%20000]+flag);
}
if(i>10000)f[(i-10000)%20000]=2e9;
if(i-w[now-1]>20000&&w[now]-i>40000)i+=20000;
}
int minn=1e9;
rep0(i,t+1)minn=min(f[(l-i)%20000],minn);
cout<<minn<<endl;
return 0;
}
请问谁知道我为什么第6个点错了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MaxM=100;
const int MaxL=2520;

int L,S,T,M,A[MaxM+1],Stone[MaxM*MaxL+1],F[MaxM*MaxL+1];

void init()
{
cin>>L;
cin>>S>>T>>M;
for(int i=1;i<=M;i++)
cin>>A[i];
sort(A+1,A+1+M);
}

void compress()
{
for(int i=1;i<=M;i++)
{
A[i]=A[i-1]+(A[i]-A[i-1])%MaxL;
Stone[A[i]]=1;
}
}

int dp()
{
memset(F,127,sizeof(F));
F[0]=0;
for(int i=S;i<=MaxM*MaxL;i++)
for(int j=S;j<=T;j++)
if(i>=j)
F[i]=min(F[i],F[i-j]+Stone[i]);
return F[MaxM*MaxL];
}

int main()
{
init();
compress();
cout<<dp()<<'\n';
}