喜水青蛙

喜水青蛙

题目描述

总是喜欢在水里嬉戏的青蛙，某天要过河拜访一位朋友。
已知河道中长满了带刺的不知名生物，能通过的路只有一条直线，长度为L。
直线上随机分布着m块石头。青蛙的最小跳跃距离是s，最大跳跃距离是t。
青蛙想要尽可能的少踩石头，那么它通过河道最少会踩到多少石头？

输入描述：

多组数据输入，其中每组数据：
第一行输入1个整数L(1<=L<=1e9)。
第二行输入3个整数：s、t、m(1<=s<=t<=10，1<=m<=100)。
第三行输入m个不同的整数，表示m个石子在数轴上的分布位置。
每行所有相邻整数用空格隔开。

输出描述：

输出青蛙过河最少会踩到的石子数量，
每组输入数据对应的输出结果单独成行。

输入样例：

10
2 3 5
2 3 5 6 7

输出样例：

2

代码

#include<stdio.h>

int min(int x, int y)
{
    return x<y?x:y;
}

int gcd(int x,int y){
    if(y==0)return x;
    return gcd(y,x%y);
}

int lcm(int x, int y){
    return x*y/gcd(x,y);
}

void quicksort(int *a,int left,int right)
{
    if(left>right)
    {
        return ;
    }
    int i=left;
    int j=right;
    int key=a[left];
    while(i!=j)
    {
        while(a[j]>=a[left]&&i<j)
        {
            j--;
        }
        while(a[i]<=a[left]&&i<j)
        {
            i++;
        }
        int s;
        s=a[i];
        a[i]=a[j];
        a[j]=s;
    }
    a[left]=a[i];
    a[i]=key;
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
}

int main(){
    int l,s,t,m;
    int a[101],b[101],f[20000],flag[20000];
    scanf("%d %d %d %d",&l,&s,&t,&m);
    int k=lcm(s,t);
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    if(s==t){
        int sum=0;
        for(int i=1;i<=m;i++)if(a[i]%s==0)sum++;
        printf("%d",sum);
        return 0;
    }
    a[m+1]=l;
    quicksort(a,0,m+1);
    for(int i=1;i<=m+1;i++){
        if(a[i]-a[i-1]>=2*k)b[i]=(a[i]-a[i-1])%k+k;
        else b[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=m+1;i++){
        a[i]=a[i-1]+b[i];
        flag[a[i]]=1;
    }
    flag[a[m+1]]=0;
    for(int i=1;i<=a[m+1]+t+1;i++){
        f[i]=0x3fffffff;
        for(int j=s;j<=min(i,t);j++){
            f[i]=min(f[i],f[i-j]+flag[i]);
        }
    }
    printf("%d",f[a[m+1]+t+1]);
    return 0;
}