#P3849. 第3题-魔法学院
-
1000ms
Tried: 110
Accepted: 19
Difficulty: 6
所属公司 :
拼多多
时间 :2025年9月28日
-
算法标签>动态规划
第3题-魔法学院
解题思路
本题要求在总法力值不超过 M 的前提下,使得到的魔法强度之和最大。约束包括:课程必须按顺序学习(只能学前缀),每门课必须在某一层完整学习,楼层会同时放大收益与消耗,并且只在上行切换楼层时需要额外的法力消耗(等于楼层差),下行或不变不额外消耗。
核心做法是动态规划(DP),状态带上“已学到第几门课”“当前所处楼层”“已花费法力”。
设楼层从 1..m 编号、课程从 1..n。令:
gain(i, j) = power[i] * bonus[j]:第i门课在第j层的强度增益;cost(i, j) = mana[i] * bonus[j]:第i门课在第j层的法力消耗;- 从上一门所在楼层
p到当前楼层j的切换代价为max(0, j - p)(只上行收费)。
定义 DP:
dp[j][c]表示“在处理完当前课程的阶段(已学习某个前缀),且最后一门课在楼层j,总消耗为c时的最大强度”。- 采用两层滚动:上一门课层
prev[j][c]→ 当前门课层curr[j][c],从而把空间压到O(m*M)。
初始化(处理第 1 门课):
- 对每个楼层
j,若cost(1, j) ≤ M,则prev[j][cost(1, j)] = gain(1, j)(首门没有切换代价)。
转移(第 i ≥ 2 门课):
-
对每个
p、每个花费c,若prev[p][c]有效,再尝试把第i门放在楼层j:extra = cost(i, j) + max(0, j - p)- 若
c + extra ≤ M,则curr[j][c + extra] = max(curr[j][c + extra], prev[p][c] + gain(i, j))
答案:在每一轮更新后都可统计 max_j max_c dp[j][c];并与 0 取最大(允许一门不学)。若第一门在任意楼层都超预算,则输出 0,与题意一致(样例 1)。
该建模天然满足“必须按顺序”,因为第 i 门的状态只能由第 i-1 门转移而来,因此只会选择一个前缀(可在任意课程处停止),不会跳课。
复杂度分析
- 状态数约为
O(m*M),每门课的转移需要枚举上一个楼层与当前楼层,故总时间复杂度为O(n * m * m * M);在数据范围n≤100, m≤5, M≤1000下,约2.5×10^6次转移,完全可行。 - 空间复杂度使用滚动数组为
O(m*M),约5×1000级别,内存友好。
代码实现
Python
# -*- coding: utf-8 -*-
import sys
INF_NEG = -10**9
def compute_max_strength(n, m, M, power, mana, bonus):
# 为了书写方便,转为 1-based
power = [0] + power
mana = [0] + mana
bonus = [0] + bonus
# prev[j][c]: 已学到当前阶段的最后一门在楼层 j、总花费 c 的最大强度
prev = [[INF_NEG] * (M + 1) for _ in range(m + 1)]
ans = 0
# 处理第 1 门课(首门不需要切换代价)
for j in range(1, m + 1):
c = mana[1] * bonus[j]
g = power[1] * bonus[j]
if c <= M:
prev[j][c] = max(prev[j][c], g)
ans = max(ans, g)
# 逐门处理第 2..n 门
for i in range(2, n + 1):
curr = [[INF_NEG] * (M + 1) for _ in range(m + 1)]
for p in range(1, m + 1): # 上一门所在楼层
row = prev[p]
for c_prev in range(M + 1): # 之前花费
if row[c_prev] == INF_NEG:
continue
base = row[c_prev]
for j in range(1, m + 1): # 当前门所在楼层
extra = mana[i] * bonus[j] + max(0, j - p) # 上行切换才有代价
c_new = c_prev + extra
if c_new <= M:
g_new = base + power[i] * bonus[j]
if g_new > curr[j][c_new]:
curr[j][c_new] = g_new
ans = max(ans, g_new)
prev = curr
return max(ans, 0)
def main():
data = list(map(int, sys.stdin.read().strip().split()))
# 依次读取
idx = 0
n, m, M = data[idx], data[idx+1], data[idx+2]; idx += 3
power = data[idx:idx+n]; idx += n
mana = data[idx:idx+n]; idx += n
bonus = data[idx:idx+m]; idx += m
print(compute_max_strength(n, m, M, power, mana, bonus))
if __name__ == "__main__":
main()
Java
import java.util.*;
/**
* ACM 风格,类名 Main
* 动态规划:状态为最后一门所在楼层与总花费,滚动数组优化空间
*/
public class Main {
static final int INF_NEG = -1000000000;
// 外部函数:完成题意逻辑
public static int computeMaxStrength(int n, int m, int M, int[] power, int[] mana, int[] bonus) {
// 调整为 1-based
int[] pw = new int[n + 1];
int[] ma = new int[n + 1];
int[] bo = new int[m + 1];
for (int i = 1; i <= n; i++) pw[i] = power[i - 1];
for (int i = 1; i <= n; i++) ma[i] = mana[i - 1];
for (int j = 1; j <= m; j++) bo[j] = bonus[j - 1];
int[][] prev = new int[m + 1][M + 1];
for (int j = 1; j <= m; j++) Arrays.fill(prev[j], INF_NEG);
int ans = 0;
// 第 1 门课
for (int j = 1; j <= m; j++) {
int c = ma[1] * bo[j];
int g = pw[1] * bo[j];
if (c <= M) {
prev[j][c] = Math.max(prev[j][c], g);
ans = Math.max(ans, g);
}
}
// 第 2..n 门
for (int i = 2; i <= n; i++) {
int[][] curr = new int[m + 1][M + 1];
for (int j = 1; j <= m; j++) Arrays.fill(curr[j], INF_NEG);
for (int p = 1; p <= m; p++) { // 上一门楼层
for (int cPrev = 0; cPrev <= M; cPrev++) {
int base = prev[p][cPrev];
if (base == INF_NEG) continue;
for (int j = 1; j <= m; j++) { // 当前门楼层
int extra = ma[i] * bo[j] + Math.max(0, j - p);
int cNew = cPrev + extra;
if (cNew <= M) {
int gNew = base + pw[i] * bo[j];
if (gNew > curr[j][cNew]) {
curr[j][cNew] = gNew;
ans = Math.max(ans, gNew);
}
}
}
}
}
prev = curr;
}
return Math.max(ans, 0);
}
// 主函数:完成输入输出
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), M = sc.nextInt();
int[] power = new int[n];
int[] mana = new int[n];
int[] bonus = new int[m];
for (int i = 0; i < n; i++) power[i] = sc.nextInt();
for (int i = 0; i < n; i++) mana[i] = sc.nextInt();
for (int j = 0; j < m; j++) bonus[j] = sc.nextInt();
int ans = computeMaxStrength(n, m, M, power, mana, bonus);
System.out.println(ans);
}
}
C++
#include <bits/stdc++.h>
using namespace std;
/*
* 动态规划:
* dp[j][c] = 处理到当前课程,最后一门在楼层 j,花费 c 的最大强度
* 仅在上行切换时增加楼层差的代价
* 两层滚动减少空间
*/
const int INF_NEG = -1000000000;
int compute_max_strength(int n, int m, int M,
const vector<int>& power,
const vector<int>& mana,
const vector<int>& bonus) {
// 1-based 拷贝
vector<int> pw(n + 1), ma(n + 1), bo(m + 1);
for (int i = 1; i <= n; ++i) pw[i] = power[i - 1];
for (int i = 1; i <= n; ++i) ma[i] = mana[i - 1];
for (int j = 1; j <= m; ++j) bo[j] = bonus[j - 1];
vector<vector<int>> prev(m + 1, vector<int>(M + 1, INF_NEG));
int ans = 0;
// 第 1 门课
for (int j = 1; j <= m; ++j) {
int c = ma[1] * bo[j];
int g = pw[1] * bo[j];
if (c <= M) {
prev[j][c] = max(prev[j][c], g);
ans = max(ans, g);
}
}
// 第 2..n 门
for (int i = 2; i <= n; ++i) {
vector<vector<int>> curr(m + 1, vector<int>(M + 1, INF_NEG));
for (int p = 1; p <= m; ++p) { // 上一门楼层
for (int cPrev = 0; cPrev <= M; ++cPrev) {
int base = prev[p][cPrev];
if (base == INF_NEG) continue;
for (int j = 1; j <= m; ++j) { // 当前门楼层
int extra = ma[i] * bo[j] + max(0, j - p);
int cNew = cPrev + extra;
if (cNew <= M) {
int gNew = base + pw[i] * bo[j];
if (gNew > curr[j][cNew]) {
curr[j][cNew] = gNew;
ans = max(ans, gNew);
}
}
}
}
}
prev.swap(curr);
}
return max(ans, 0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, M;
if (!(cin >> n >> m >> M)) return 0;
vector<int> power(n), mana(n), bonus(m);
for (int i = 0; i < n; ++i) cin >> power[i];
for (int i = 0; i < n; ++i) cin >> mana[i];
for (int j = 0; j < m; ++j) cin >> bonus[j];
int ans = compute_max_strength(n, m, M, power, mana, bonus);
cout << ans << "\n";
return 0;
}
题目内容
多多进入了魔法学院学习,学院有 n 门不同的魔法课程,每门课程都有其独特的属性:
power[i]:学习这门课程能提升的魔法强度
mana[i]:学习这门课程需要消耗的法力值
学院的教学楼有m 层,每层有不同的环境加成系数 bonus[i](1≤bonus[i]≤3)。
多多总共有 M 点初始法力值。
特殊规则:
1.顺序学习:多多必须按顺序学习课程(必须先学课程 1,再学课程 2,以此类推)。
2.楼层绑定:每门课程只能在某一层完整学习,不能跨层。
3.强度加成:在第 j 层学习第 i 门课程时,获得的实际魔法强度为power[i] × bonus[j]。
4.法力消耗:在第 j 层学习第 i 门课程时,消耗的实际法力值为 mana[i] × bonus[j]。
5.切换代价:多多可以在不同楼层之间切换课程,第一次学习选择楼层没有切换代价,但每次切换可能会额外消耗楼层高度差的法力值。如果从低楼层切换到高楼层,比如从 1 层切换到 4 层,消耗 3 点法力,如果从高楼层切换到低楼层,则不会消耗额外的法力
请求出在满足法力值限制(总法力消耗不超过 M )的条件下,多多能获得的最大魔法强度总和(无需学完所有课程)。
输入描述
第一行三个整数 n,m,M(1≤n≤100,1≤m≤5,1≤M≤1000)
第二行 n 个整数,表示 power[i](1≤power[i]≤100)
第三行 n 个整数,表示 mana[i](1≤mana[i]≤100)
第四行 m 个整数,表示 bonus[j](1≤bonus[j]≤3)
输出描述
输出一个整数,表示能获得的最大魔法强度总和。如果无法完成任何课程(例如,第一门课程在任何一层学习的法力消耗都超过 M ),则输出 0 。
补充说明
对于 20 %的数据:n≤10,1≤m≤5,1≤M≤1000
对下 60 % 的数据:n≤30,1≤m≤5,1≤M≤1000
对于 100 %的数据:1≤n≤100,1≤m≤5,1≤M≤1000
样例1
输入
1 1 5
10
5
2
输出
0
说明
1 门课程,1 层楼,初始法力值 5 课程强度 10,消耗 5 ,楼层加成 2 实际消耗 =5×2=10>5 (无法学习)
样例2
输入
2 2 20
5 10
2 3
2 3
输出
45
说明
2 门课程,2 层楼,初始法力值 [2,3]
课程强度: [5,10],消耗: [2,3],楼层加成: [2,3]
可能的方案:
都在 1 层(加成 2 ):消耗 =2×2+3×2=4+6=10,强度 =5×2+10×2=10+20=30
都在 2 层(加成 3):消耗 =2×3+3×3=6+9=15,强度 =5×3+10×3=15+30=45
课程 1 在 1 层,课程 2 在 2 层:切换消耗 =2−1=1,总消耗 =2×2+3×3+1=4+9+1=14,强度 =5×2+10×3=10+30=40
课程 1 在 2 层,课程 2 在 1 层:切换消耗 =0,总消耗 =2×3+3×2=6+6=12,强度 =5×3+10×2=15+20=35