[HUSTFC 2023] 简单的加法乘法计算题

Luogu

IDLGP9769

Time1000ms

Memory512MB

DifficultyP3

动态规划 DP单调队列2023O2优化动态规划优化高校校赛

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$ 的最少操作次数。 ## Input 第一行包含三个整数 $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)$。 ## Output 输出一个整数，表示让 $x$ 变成 $y$ 的最少操作次数。在题目条件下可知一定能将 $x$ 变成 $y$。 [samples]

Samples

Input #1

10 3 1
2

Output #1

Input #2

100 6 3
2 3 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[HUSTFC 2023] 简单的加法乘法计算题",
    "description": {
      "content": "JokerShaco 有一个数字 $x$，最开始 $x=0$，他想要把 $x$ 变成 $y$。为了达到这个目标，他可以利用两个集合 $A$ 和 $B$。其中集合 $A$ 包含 $n$ 个元素，分别是从 $1$ 到 $n$ 的所有正整数；集合 $B$ 包含 $m$ 个元素。每次它可以对 $x$ 进行如下任意次操作： - 选择 $A$ 中的一个元素 $a$，令 $x$ 加上 $a$。 - 选择 $B$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9769"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "JokerShaco 有一个数字 $x$，最开始 $x=0$，他想要把 $x$ 变成 $y$。为了达到这个目标，他可以利用两个集合 $A$ 和 $B$。其中集合 $A$ 包含 $n$ 个元素，分别是从 $1$ 到 $n$ 的所有正整数；集合 $B$ 包含 $m$ 个元素。每次它可以对 $x$ 进行如下任意次操作：\n- 选择 $A$ 中的一个元素 $a$，令 $x$ 加上 $a$。\n- 选择 $B$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments