f[i] = min{f[i - j]} s<=j<=t i位置没有石子 = min{f[i - j]} + 1 s<=j<=t i位置有石子 可是，本题的L可以达到10^9，即使压缩了数组空间，时间也不允许。
注意到题目的石子数量不到100个，因此，当L达到很大时，一定存在很长的一段或几段没有石子，在S不等于T的时候，青蛙在这里面怎么跳都不会踩到石头，如果可以把这些“空长条”去掉，那么实际需要计算的长度就可以大大降低。
如何确定空长条的范围呢？
题目有说s,t<=10。读者可以估计一下，本人认为长度大于100就可以看作空长条了。RQNOJ上有人专门对这个问题做了分析，有兴趣的读者可以去看一下。 需要注意的是，题目没有说明石头的位置是递增输入的，因此别忘了排序。
排序后，就可以逐一检查两个石头之间的距离，如果大于100，就把后面的石头全部向前移动，使这一段变成刚好100.对于L，其实它只要是最后一个石头的位置+t就可以了。
然后可以利用上面的关系式进行DP，最后在f[最后一个石头的位置]~[最后一个石头的位置+t]中选取最小值输出即可。
不过，在测试的时候，发现使用上面的方法有两个数据不能通过。最后发现那两个数据的s=t。在这种情况下，空长条就不能被移除，而应之间判断每个石子的位置是否可以被s整除。
代码如下：
C语言: 高亮代码由发芽网提供
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int s,t,m;
long l;
int f[20000];
_Bool havestone[20000];
long stone[102];
int cmp(const void *a,const void *b)
{
return (*(long *)a - *(long *)b);
}
int main()
{
long i,j;
long del;
int min;
scanf("%ld%d%d%d",&l,&s,&t,&m);
for(i = 1;i <= m;i ++) scanf("%ld",&stone[i]);
stone[0] = 0; //方便处理
qsort(stone,m + 1,sizeof(long),cmp);
if(s == t)
{
j = 0;
for(i = 1;i <= m;i ++)
if(stone[i] % s == 0) j ++;
printf("%ld\n",j);
exit(0);
}
//压缩“空长段”
for(i = 1;i <= m;i ++)
{
if(stone[i] - stone[i - 1] > 100)
{
del = stone[i] - stone[i - 1] - 100;
for(j = i;j <= m;j ++)
{
stone[j] -= del;
}
}
}
if(stone[m] + 12 < l) l = stone[m] + 12;
for(i = 1;i <= m;i ++)
havestone[stone[i]] = 1;
//DP过程
f[0] = 0;
for(i = 1;i <= l + t;i ++)
{
min = INT_MAX;
for(j = s;j <= t;j ++)
{
if((i - j) >= 0 && f[i - j] < min) min = f[i - j];
}
f[i] = min;
if(havestone[i]) f[i] ++;
}
min = INT_MAX;
for(i = stone[m];i <= l + t;i ++)
if(f[i] < min) min = f[i];
printf("%d\n",min);
return 0;
}
#include <stdlib.h>
#include <limits.h>
int s,t,m;
long l;
int f[20000];
_Bool havestone[20000];
long stone[102];
int cmp(const void *a,const void *b)
{
return (*(long *)a - *(long *)b);
}
int main()
{
long i,j;
long del;
int min;
scanf("%ld%d%d%d",&l,&s,&t,&m);
for(i = 1;i <= m;i ++) scanf("%ld",&stone[i]);
stone[0] = 0; //方便处理
qsort(stone,m + 1,sizeof(long),cmp);
if(s == t)
{
j = 0;
for(i = 1;i <= m;i ++)
if(stone[i] % s == 0) j ++;
printf("%ld\n",j);
exit(0);
}
//压缩“空长段”
for(i = 1;i <= m;i ++)
{
if(stone[i] - stone[i - 1] > 100)
{
del = stone[i] - stone[i - 1] - 100;
for(j = i;j <= m;j ++)
{
stone[j] -= del;
}
}
}
if(stone[m] + 12 < l) l = stone[m] + 12;
for(i = 1;i <= m;i ++)
havestone[stone[i]] = 1;
//DP过程
f[0] = 0;
for(i = 1;i <= l + t;i ++)
{
min = INT_MAX;
for(j = s;j <= t;j ++)
{
if((i - j) >= 0 && f[i - j] < min) min = f[i - j];
}
f[i] = min;
if(havestone[i]) f[i] ++;
}
min = INT_MAX;
for(i = stone[m];i <= l + t;i ++)
if(f[i] < min) min = f[i];
printf("%d\n",min);
return 0;
}
