[GDKOI2024 普及组] 刷野 III

Luogu
IDLGP10074
Time2000ms
Memory512MB
DifficultyP6
2024广东O2优化
Zayin 是一个与怪物战斗的巫师,这次他将面临 $n$ 个站成一排的怪物,其中第 $i$ 个怪物的生命值是 $a_i$。 但是由于某种神秘原因,Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 $n$ 的排列 $p$,Zayin 每次攻击第 $i$ 只怪物时,实际上是在攻击第 $p_i$ 只怪物。 Zayin 每次可以选择一个 $[1, n]$ 的整数 $k$,让第 $p_k$ 只怪物的血量减少 $1$ 点,当某只怪物的血量小于等于 $0$ 时这只怪物死亡。 然而 Zayin 并不知道这个排列 $p$ 具体是什么,也无法看到每个怪物剩余的具体血量,仅可以知道每次攻击完后怪物是否死亡。 现在 Zayin 想知道,在他采取最优策略的情况下,最多需要攻击多少次,才可以杀死 $m$ 只怪物。 ## Input 输入的第一行包含两个正整数 $n, m(1 \leq m \leq n \leq 2000)$,$n$ 表示怪物的个数,$m$ 表示 Zayin 所需要击杀的怪物个数。 输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n(1 \leq a_i \leq 10^9)$,$a_i$ 表示第 $i$ 只怪物的血量。 ## Output 输出一个整数,最少的攻击次数。 [samples] ## Note **【样例解释】** 在第一个样例,Zayin 会一直攻击某一只怪物,直到怪物死亡。 在第二个样例,Zayin 先攻击某一个怪物 $10$ 次,如果没有死亡,则说明攻击的是 $30$ 血的怪物。这时 Zayin 会选择攻击第二只怪物,攻击 $10$ 次后另一只怪物一定死亡,故最差需要 $20$ 次。 **【数据范围】** 对于 $10\%$ 的数据,$1 \leq n, m \leq 5$。 对于另外 $20\%$ 的数据,所有 $a_i$ 全部相等。 对于另外 $30\%$ 的数据,$1 \leq m \leq n \leq 500$。 对于 $100\%$ 的数据,$1 \leq m \leq n \leq 2000$,$1 \leq a_i \leq 10^9$。
Samples
Input #1
2 1
10 15
Output #1
15
Input #2
2 1
10 30
Output #2
20
API Response (JSON)
{
  "problem": {
    "name": "[GDKOI2024 普及组] 刷野 III",
    "description": {
      "content": "Zayin 是一个与怪物战斗的巫师,这次他将面临 $n$ 个站成一排的怪物,其中第 $i$ 个怪物的生命值是 $a_i$。 但是由于某种神秘原因,Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 $n$ 的排列 $p$,Zayin 每次攻击第 $i$ 只怪物时,实际上是在攻击第 $p_i$ 只怪物。 Zayin 每次可以选择一个 $[1, n]$ 的整数 $k$,让第 $p",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10074"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Zayin 是一个与怪物战斗的巫师,这次他将面临 $n$ 个站成一排的怪物,其中第 $i$ 个怪物的生命值是 $a_i$。\n\n但是由于某种神秘原因,Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 $n$ 的排列 $p$,Zayin 每次攻击第 $i$ 只怪物时,实际上是在攻击第 $p_i$ 只怪物。\n\nZayin 每次可以选择一个 $[1, n]$ 的整数 $k$,让第 $p...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments