新鲜出炉的比赛题目，可惜比赛时候在补作业没法打比赛只能赛后补了XD

首先观察题意，可以发现$x$从$0$到$a$中间具体取法并不会影响后面的步骤，满足DP无后效性，考虑DP。

可以定义$dp_i$为$x$从$0$到$i$的最小步数，目标状态为$dp_y$

然后就可以推出两种状态转移：

1. 选择A中元素转移，$dp_i = \min_{k=1}^{n}\{dp_{i – k}\} + 1$
2. 选择B中元素转移，$dp_i = \min_{k=1}^{m}\{dp_{i / B_k}\} + 1$

但数据范围$1 \le n, y \le 5 \times 10 ^ 6$，暴力枚举复杂度$O(ny + ym)$显然会TLE。

这时候发现$dp_i$只与$dp_{i-1}$到$dp_{i – n}$中最小值有关，显然可以用单调队列优化，因为$1 \le m \le 10$所以暴力枚举B中元素没问题，复杂度为$O(y)$，能够AC。

AC代码如下：

#include <cstdio>
#include <queue>

using namespace std;
inline int rd() {
    int ret = 0, flag = 1;
    char c = getchar();
    for (; c > '9' || c < '0'; c = getchar())
        if (c == '-')
            flag = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        ret = ret * 10 + (c - '0');
    return ret * flag;
}
const int MAXY = 5e6 + 10;
int B[11];
int dp[MAXY];
int main() {
    int y = rd();
    int n = rd();
    int m = rd();
    for (int i = 1; i <= m; ++i) {
        B[i] = rd();
    }
    deque<int> q;
    q.push_back(0);
    for (int i = 1; i <= y; ++i) {
        // 单调队列
        while (!q.empty() && i - q.front() > n) {
            q.pop_front();
        }
        dp[i] = dp[q.front()] + 1;
        // 枚举B中元素转移
        for (int j = 1; j <= m; ++j) {
            if (i % B[j] != 0) {
                continue;
            }
            dp[i] = min(dp[i], dp[i / B[j]] + 1);
        }
        // 单调队列
        while (!q.empty() && dp[q.back()] >= dp[i]) {
            q.pop_back();
        }
        q.push_back(i);
    }
    printf("%d\n", dp[y]);
    return 0;
}