解题思路
本题是一个带衰减约束的调度优化问题。有 n 个菌子(n≤15),每个菌子加工需 5 小时,总时间不超过 total 小时。每个菌子 i 有初始价值 vi 和衰减速度 di,若在第 j 个被加工(j 从 0 开始),实际价值为 vi−di×j×5。若实际价值 ≤0,则跳过不加工。求最大总价值。
核心观察:最优加工顺序是确定的——在所选菌子集合固定的情况下,应按照衰减速度 di 降序加工(衰减快的先加工,减少等待带来的损失)。这可以通过交换相邻菌子的贪心论证:若 da>db,则先加工 a 后加工 b 总是优于反过来。
基于此,算法为:
- 将所有菌子按 di 降序排序;
- 进行 0/1 背包式 DP:dp[j] 表示已加工 j 个菌子时的最大总价值;