#P3350. 第2题-放他一马
-
1000ms
Tried: 307
Accepted: 36
Difficulty: 6
所属公司 :
美团
时间 :2025年8月9日-开发岗
-
算法标签>动态规划
第2题-放他一马
思路概述
击败第 i 只怪物的额外加成只与“已击败数量对 10 取模”有关,而与具体击败了谁、击败了多少整十无关。因此可用动态规划,把“已击败数量 mod 10”作为状态,线性推进。
状态设计
令 dp[m] 表示在处理完当前怪物之前,已击败数量 ≡ m (mod 10) 时能获得的最大经验值(滚动数组维护上一只怪物处理后的状态)。
转移
处理第 i 只怪物、生命为 a_i:
- 放走:
ndp[m] = max(ndp[m], dp[m] + i) - 击败:新的余数
nm = (m + 1) % 10,收益gain = a_i * (1 + nm),转移ndp[nm] = max(ndp[nm], dp[m] + gain)
初始:dp[0] = 0,其余为 -∞。答案为处理完 n 只后 max(dp)。
正确性说明
- 任何时刻,未来每次“击败”只会把已击败数量模 10 增加 1,且本次收益只取决于新的余数
nm与a_i,与具体击败了多少整十(10、20、…)无关。 - 因此,以“已击败数 mod 10”为充分状态即可,不会丢失决策必要信息。线性 DP 枚举两种选择覆盖了所有方案,取最大值即为最优。
实现细节
- 负无穷使用一个足够小的常量,如
-9e18(Java/C++)或-10**30(Python)。 i必须是题目原编号(1 开始),用于“放走”收益。- 每步先拷贝/重置
ndp,完成两类转移后覆盖dp。
复杂度分析
- 状态数恒为 10,每个怪物转移 10 个状态:时间复杂度
O(10n) = O(n); - 仅用两个长度为 10 的数组滚动:空间复杂度
O(10) = O(1)。 - 注意使用 64 位整型(Python int / Java long / C++ long long)。
代码
Python
import sys
def solve():
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
return
n = data[0]
a = data[1:]
INF = -10**30
dp = [INF] * 10
dp[0] = 0 # 初始击败数为 0(模 10 为 0)
for i, val in enumerate(a, start=1):
ndp = [INF] * 10
for m in range(10):
if dp[m] == INF:
continue
# 放走:已击败数模不变
if dp[m] + i > ndp[m]:
ndp[m] = dp[m] + i
# 击败:模数 +1
nm = (m + 1) % 10
gain = val * (1 + nm) # a_i * (1 + ((k+1) mod 10))
v = dp[m] + gain
if v > ndp[nm]:
ndp[nm] = v
dp = ndp
print(max(dp))
if __name__ == "__main__":
solve()
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
// 负无穷:选个足够小的值,避免后续加法溢出
long NEG = Long.MIN_VALUE / 4;
// dp[m]:到当前为止,已击败数 ≡ m (mod 10) 的最大经验值
long[] dp = new long[10];
Arrays.fill(dp, NEG);
dp[0] = 0;
for (int i = 0; i < n; i++) {
long[] ndp = new long[10];
Arrays.fill(ndp, NEG);
for (int m = 0; m < 10; m++) {
if (dp[m] == NEG) continue;
// 选择放走第 i+1 只怪:已击败数模不变,收益 + (i+1)
ndp[m] = Math.max(ndp[m], dp[m] + (long)(i + 1));
// 选择击败第 i+1 只怪:模数 +1,收益 a[i] * (1 + ((m+1) mod 10))
int nm = (m + 1) % 10;
long gain = a[i] * (1 + nm);
ndp[nm] = Math.max(ndp[nm], dp[m] + gain);
}
dp = ndp;
}
long ans = dp[0];
for (int m = 1; m < 10; m++) ans = Math.max(ans, dp[m]);
System.out.println(ans);
}
}
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
const long long NEG = (long long)-9e18; // 负无穷
long long dp[10], ndp[10];
for (int m = 0; m < 10; ++m) dp[m] = NEG;
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int m = 0; m < 10; ++m) ndp[m] = NEG;
for (int m = 0; m < 10; ++m) {
if (dp[m] == NEG) continue;
// 放走:加 i+1
ndp[m] = max(ndp[m], dp[m] + (long long)(i + 1));
// 击败:模 +1,收益 a_i * (1 + nm)
int nm = (m + 1) % 10;
long long gain = a[i] * (1 + nm);
ndp[nm] = max(ndp[nm], dp[m] + gain);
}
for (int m = 0; m < 10; ++m) dp[m] = ndp[m];
}
long long ans = dp[0];
for (int m = 1; m < 10; ++m) ans = max(ans, dp[m]);
cout << ans << '\n';
return 0;
}
题目内容
小美会按照编号从小到大的顺序依次遇到 n 只怪物(编号为 1 ~ n),怪物 i(1≤i≤n) 的生命为 ai 。
对于每只怪物,小美都可以选择放走 Ta 或者击败 Ta。
-
如果放走怪物,小美将获得 i 点经验值。
-
如果击败怪物,小美将获得 ai 点经验值,同时将额外获得 (x mod 10)×ai 点经验值,x 为击败怪物数量(包括这一个怪物)。
求小美最多可以从这 n 个怪物中获得的经验值。
输入描述
第一行输入一个整数 n(1≤n≤2×105) 表示怪物数。
第二行输入 n 个整数 ai(1≤ai≤109) 表示怪物的生命。
输出描述
输出一个整数表示小美可以获得最高的经验值。
样例1
输入
3
5 3 2
输出
27
说明
第一个怪物选择击败获得 5+5×1=10 的经验值,第二个怪物选择击败获得 3+3×2=9 的经验值,第三只怪物选择击败获得 2+2×3=8 的经验值,总共获得 27 的经验值。