解题思路

本题要求在总法力值不超过 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$