秋实-Allenyou的小窝

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

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

可以定义$d{p}_i$为$x$从$0$到$i$的最小步数，目标状态为$d{p}_y$

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

1. 选择 A 中元素转移，$d{p}_i=\underset{k=1}{\overset{n}{min}}d{p}_{i-k}+1$
2. 选择 B 中元素转移，$d{p}_i=\underset{k=1}{\overset{m}{min}}d{p}_{i/B_k}+1$

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

这时候发现$d{p}_i$只与$d{p}_{i-1}$到$d{p}_{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;
}