[CSP-X2025 山东] 勇者斗恶龙

Luogu

IDLGB4428

Time1000ms

Memory512MB

DifficultyP3

动态规划 DP2025山东CSP-X 小学组

为了拯救世界，勇者们终于来到了恶龙面前。现在有 $n$ 位勇者排成一列准备迎战恶龙，勇者们位置事先已经排好不能改变，第 $i$ 位勇者的初始能力值为 $a_i$，且每提升 1 点能力值，需要花费 $b_i$ 的代价。但是如果任意相邻的两位勇者能力值相同，他们之间就会产生冲突从而导致战力大幅下降。你可以通过提升勇者的能力值，来确保队伍中任意相邻的两名勇者能力值都不相同，从而以完美的状态迎接恶龙。你只需要计算并输出满足条件所花费的最小的总代价。 ## Input 第一行一个整数 $n$，表示勇士的数量。接下来 $n$ 行，每行两个数 $a_i, b_i$ 分别表示第 $i$ 位勇士的初始能力值和每提升 1 点能力值需要花费的代价。 ## Output 一行一个整数表示答案。 [samples] ## Note 【样例 1 解释】如果把第一个勇者能力值增加 $1$，三位勇者的能力值变成 $(2, 1, 2)$，花费代价 $5$。如果把第二个勇者能力值增加 $2$，三位勇者的能力值变为 $(1, 3, 2)$，花费代价 $4$。如果把第二个勇者能力值增加 $1$，第三个勇者的能力值增加 $1$，三位勇者的能力值变为 $(1, 2, 3)$，花费代价 $5$。因此最小花费的代价为 $4$，可以证明没有更小的代价能满足条件。【样例 2 解释】可以分别提升第一位和第三位勇士的能力值 1 点，最小总花费为 30。【样例 3】见选手目录下的 `hero/ex_hero3.in` 与 `hero/ex_hero3.ans`。该样例满足数据范围中测试点第 9~10 的限制。【样例 4】见选手目录下的 `hero/ex_hero4.in` 与 `hero/ex_hero4.ans`。该样例满足数据范围中测试点第 11~12 的限制。【样例 5】见选手目录下的 `hero/ex_hero5.in` 与 `hero/ex_hero5.ans`。该样例满足数据范围中测试点第 13~20 的限制。【数据范围】 ::cute-table{tuack} | 测试点 | $n \le$ | $1 \le a_i, b_i \le$ | 特殊性质 | |:------:|:-------------:|:----------------------:|:--------:| | $1\sim 4$ | $10$ | $10$ | 无 | | $5\sim 8$ | $100$ | $10$ | 无 | | $9\sim 10$ | $10^5$ | $10$ | $a_i = 1$ | | $11\sim 12$ | $10^5$ | $10$ | $b_i = 1$ | | $13\sim 20$ | $2 \times 10^5$ | $10^9$ | 无 |

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CSP-X2025 山东] 勇者斗恶龙",
    "description": {
      "content": "为了拯救世界，勇者们终于来到了恶龙面前。 现在有 $n$ 位勇者排成一列准备迎战恶龙，勇者们位置事先已经排好不能改变，第 $i$ 位勇者的初始能力值为 $a_i$，且每提升 1 点能力值，需要花费 $b_i$ 的代价。 但是如果任意相邻的两位勇者能力值相同，他们之间就会产生冲突从而导致战力大幅下降。 你可以通过提升勇者的能力值，来确保队伍中任意相邻的两名勇者能力值都不相同，从而以完美的状态迎",
      "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": "LGB4428"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "为了拯救世界，勇者们终于来到了恶龙面前。\n\n现在有 $n$ 位勇者排成一列准备迎战恶龙，勇者们位置事先已经排好不能改变，第 $i$ 位勇者的初始能力值为 $a_i$，且每提升 1 点能力值，需要花费 $b_i$ 的代价。\n\n但是如果任意相邻的两位勇者能力值相同，他们之间就会产生冲突从而导致战力大幅下降。\n\n你可以通过提升勇者的能力值，来确保队伍中任意相邻的两名勇者能力值都不相同，从而以完美的状态迎...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments