美团 · 动态规划 · 算法编程题
美团 动态规划 n ≤ 200000 时限 1 秒 / 256 MB

题目描述

小美会按照编号从小到大的顺序依次遇到 n 只怪物（编号为 1 n ），怪物 i(1 ≤ i ≤ n) 的生命为 a_i 。
对于每只怪物，小美都可以选择放走Ta或者击败Ta。
如果放走怪物，小美将获得 i 点经验值。
如果击败怪物，小美将获得 a_i 点经验值，同时将额外获得 (x mod 10) × a_i 点经验值， x 为击败怪物数量（包括这一个怪物）。
求小美最多可以从这 n 个怪物中获得的经验值。

输入输出

输入描述
第一行输入一个整数 n(1 ≤ n ≤ 2× 10^5) 表示怪物数。
第二行输入 n 个整数 a_i(1 ≤ a_i ≤ 10^9) 表示怪物的生命。
输出描述
输出一个整数表示小美可以获得最高的经验值。

样例共 1 组

样例 1 · 第一个怪物选择击败获得 5+5 × 1=10 的经验值，第二个怪物选择击败获得 3+3×2=9 的经验值，第三只怪物选择击败获得 2+2×3=8 的经验值，总共获得 27 的经验值。
输入
3
5 3 2
输出
27

算法解析依据充分

考点：数组 · 动态规划

数据规模 n ≤ 200000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 200000
  • 元素值域：a_i ≤ 1e9（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。

思路框架（动态规划 通法 · 非本题专属）

  1. 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
  2. 写转移方程：当前状态由哪些更小的状态推来。
  3. 确定初始条件与遍历顺序（保证用到的状态已算好）。
  4. 确定答案取哪个状态；数值大时全程取模。

实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。

复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)

该范式的通法易错点

  • 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
  • 初始化写错（尤其「恰好」与「至多」的初值差别）。
  • 遍历顺序与依赖方向不一致。

对照本题

  • 数据规模 n ≤ 200000，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 / 5 3 2 → 输出 27

第一个怪物选择击败获得 5+5 × 1=10 的经验值，第二个怪物选择击败获得 3+3×2=9 的经验值，第三只怪物选择击败获得 2+2×3=8 的经验值，总共获得 27 的经验值。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-美团-技术岗-第一批笔试；2025年秋招-美团-测试岗-第一批笔试；2025年秋招-美团-运维&安全岗-第一批笔试 等。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解