这道题跟过河题差不多，那些讨厌的数就相当于是河上的阻碍，如果 $a == b$ 说明每次买的零食价钱一样，只需要考虑那些数是不是 $a$ 和 $b$ 的倍数，若是则 $+1$ 。 如果 $a != b$ 那么我们可以考虑不能被 $a ~ b$ 中所表示的数有哪些，说明这些数不是讨厌的数可以触及。如果只用两个相邻的数 $p,q$ ，那么不能被表示的数的最大值是 $(p – 1)(q – 1) – 1$ ，所有大于等于 $(p – 1)(q – 1)$ 都可被 $p,q$ 表示出来，当 $p = 9,q = 10$ 时取最大值 $72$ ，因此所有大于 $72$ 的数一定可以被 $a~b$ 表示出来。当越过第 $i$ 个数时，当前总价一定大于该讨厌的数 $10$ 个数以内，同理越过第 $i+1$ 个数时，当前总价一定大于该讨厌的数 $10$ 个数以内。当相邻两个讨厌的数的距离超过了 $72$ ，我这里是取整 $(100)$ ，那么这个情况跟距离为 $100$ 的时候的情况一样，可以降低时间复杂度。

#include<bits/stdc++.h>
using namespace std;

const int N = 10010;

int T,a,b,n;
int h[N];
//w存储讨厌的数和不讨厌的数，0表示不讨厌的数，1表示讨厌的数
//f存储到达该数时，遇到的讨厌的数的个数
int w[N], f[N];

int main()
{
    scanf("%d%d%d%d",&T,&a,&b,&n);
    //如果a等于b那么就看看他讨厌的数中有没有他们的倍数若有输出+1
    if (a == b)
    {
        int res = 0;
        while (n -- )
        {
            int x;
            scanf("%d", &x);
            if (x % a == 0) res ++ ;
        }
        cout << res << '\n';
    }
    else
    {
        //先输入n个讨厌的数然后将他们从小到大排列起来
        for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);
        sort(h, h + n);
      
        int last = 0, k = 0;
//将n个讨厌的数抽象化，从1到T中，讨厌的数为1，不讨厌的数为0
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < min(h[i] - last, 100); j ++ )
                w[ ++ k] = 0;
            w[k] = 1;
            last = h[i];
        }
//计算总价到达i时最少会遇到的讨厌数的数量，这里小于等于k+10是为了防止当总价达到k时，他会再买一包10元钱的零食。
        for (int i = 1; i <= k + 10; i ++ )
        {
            f[i] = 1e9;
            for (int j = a; j <= b; j ++ )
                if (i - j >= 0)
                    f[i] = min(f[i], f[i - j] + w[i]);//
        }
        int res = 1e9;
        for (int i = k + 1; i <= k + 10; i ++ )  res = min(res, f[i]);
      
        cout << res << '\n';
    }
  
    return 0;
}