本题要求在总法力值不超过 M 的前提下,使得到的魔法强度之和最大。约束包括:课程必须按顺序学习(只能学前缀),每门课必须在某一层完整学习,楼层会同时放大收益与消耗,并且只在上行切换楼层时需要额外的法力消耗(等于楼层差),下行或不变不额外消耗。
核心做法是动态规划(DP),状态带上“已学到第几门课”“当前所处楼层”“已花费法力”。
设楼层从 1..m 编号、课程从 1..n。令:
gain(i, j) = power[i] * bonus[j]:第 i 门课在第 j 层的强度增益;cost(i, j) = mana[i] * bonus[j]:第 i 门课在第 j 层的法力消耗;多多进入了魔法学院学习,学院有 n 门不同的魔法课程,每门课程都有其独特的属性:
power[i]:学习这门课程能提升的魔法强度
mana[i]:学习这门课程需要消耗的法力值
学院的教学楼有m 层,每层有不同的环境加成系数 bonus[i](1≤bonus[i]≤3)。