本文发布于 409 天前,其中的信息可能已经有所发展或是发生改变。
新鲜出炉的比赛题目,可惜比赛时候在补作业没法打比赛只能赛后补了XD
首先观察题意,可以发现$x$从$0$到$a$中间具体取法并不会影响后面的步骤,满足DP无后效性,考虑DP。
可以定义$dp_i$为$x$从$0$到$i$的最小步数,目标状态为$dp_y$
然后就可以推出两种状态转移:
- 选择A中元素转移,$dp_i = \min_{k=1}^{n}\{dp_{i – k}\} + 1$
- 选择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; }