2023 年华中科技大学程序设计竞赛新生赛

A - 简单的加法乘法计算题

https://www.luogu.com.cn/problem/P9769?contestId=138479

题目

JokerShaco 有一个数字 $x$，最开始 $x=0$，他想要把 $x$ 变成 $y$。为了达到这个目标，他可以利用两个集合 $A$ 和 $B$。其中集合 $A$ 包含 $n$ 个元素，分别是从 $1$ 到 $n$ 的所有正整数；集合 $B$ 包含 $m$ 个元素。每次它可以对 $x$ 进行如下任意次操作：

  • 选择 $A$ 中的一个元素 $a$，令 $x$ 加上 $a$。
  • 选择 $B$ 中的一个元素 $b$，令 $x$ 乘以 $b$。

已知 $y$，$n$，$m$ 和 $B$ 中 $m$ 个元素的具体值，JokerShaco 想知道让 $x$ 变成 $y$ 的最少操作次数。

输入

第一行包含三个整数 $y\ (1\le y\le 5\cdot 10^6)$，$n\ (1\le n\le 5\cdot 10^6)$ 和 $m\ (1\le m\le 10)$，其含义如题目所述。

第二行包含 $m$ 个正整数，其中第 $i$ 个表示 $B$ 中的第 $i$ 个元素 $b_i\ (1\le b_i\le 5\cdot 10^6)$。

输出

输出一个整数，表示让 $x$ 变成 $y$ 的最少操作次数。在题目条件下可知一定能将 $x$ 变成 $y$。

样例

样例输入 #1

10 3 1
2

样例输出 #1

3

样例输入 #2

100 6 3
2 3 5

样例输出 #2

3

题解

动态规划

朴素的动态规划思想很好理解：

  • 状态表示

    • $dp_i:=$ 从 $0$ 变化到 $i$ 需要的步数

  • 状态转移

    • $A$ 操作：$dp_i:=\min\{dp_i,\min_{j=1}^{n}dp_{i-j}+1\}$
    • $B$ 操作：$dp_i:=\min\{dp_i,\min_{j=1}^{m}dp_{i/b_j}+1\}$（前提是 $i\bmod b_j = 0$）

代码片段如下：

for (int i = n + 1; i <= b; i++)
{
    for (int j = 1; j <= n; j++)
        dp[i] = min(dp[i], dp[i - j] + 1);
       for (int j = 1; j <= m; j++)
        if (i % b[j] == 0)
            dp[i] = min(dp[i], dp[i / b[j]] + 1);
}

容易得到，时间复杂度为：$O(n^2+nm)$

根据 $1\le n\le 5\cdot 10^6,\; 1\le m\le 10$，可知复杂度过高，并且瓶颈在 $A$ 操作的转换中，需要对其进行优化。

优化复杂度

从上文可知，每次转移时，需要花费 $O(n)$ 的时间来取得 $\min_{j=1}^{n}dp_{i-j}+1$ 的值，即 $dp_{i-n}\sim dp_{i-1}$ 这样一个长度为 $n$ 的滑动窗口中的最小值。

对于滑动窗口最值问题，直接使用单调队列即可解决了。单调队列的复杂度为 $O(n)$，每次查询的复杂度为 $O(1)$，因此总复杂度为：$O(n)$

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MAXN = 5e6 + 10;
int dp[MAXN];

void solve()
{
    memset(dp, 0x3f, sizeof(dp));
    int y, n, m;
    cin >> y >> n >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i++)
        cin >> b[i];
    deque<int> dque;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        dque.push_back(i);
    }
    for (int i = n + 1; i <= y; i++)
    {
        while (dque.size() && dque.front() + n < i)
            dque.pop_front();
        for (int j = 0; j < m; j++)
            if (i % b[j] == 0)
                dp[i] = min(dp[i], dp[i / b[j]] + 1);
        dp[i] = min(dp[i], dp[dque.front()] + 1);
        while (dque.size() && dp[dque.back()] > dp[i])
            dque.pop_back();
        dque.push_back(i);
    }
    cout << dp[y] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}