秋实-Allenyou 的小窝

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

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

可以定义为从到的最小步数，目标状态为

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

1. 选择 A 中元素转移，
2. 选择 B 中元素转移，

但数据范围，暴力枚举复杂度显然会 TLE。

这时候发现只与到中最小值有关，显然可以用单调队列优化，因为所以暴力枚举 B 中元素没问题，复杂度为，能够 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;
}