NOIP 2005 青蛙过河

首先想到的是简单的动态规划，时间复杂度是LM，M是t-s，转移公式是：
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;
}