题目大意

有 $M$ 栋楼，$N$ 天中每天有一个学生入住某栋楼。当一栋楼有 $x$ 个学生时，当天该楼产生的噪音为 $x$。管理员可以进行清空操作（将整栋楼的所有学生迁走），最多进行 $K$ 次。求 $N$ 天中所有楼产生的噪音总和的最小值。

算法思路

核心思想

使用动态规划，将问题分解为两个部分：

对单栋楼，给定清空次数，计算最小噪音和

在多栋楼之间分配清空次数，达到全局最优

关键步骤

1. 单栋楼的最优分段

对于一栋有 $n$ 个学生的楼，如果分配 $t$ 次清空操作，那么这 $n$ 个学生会被分成 $t+1$ 个连续段（清空操作发生在段与段之间）。

关键结论：最优策略是将 $n$ 个学生尽可能均匀地分配到 $t+1$ 个段中。

2. 数学公式推导

设：

$s = \left\lfloor \dfrac{n}{t+1} \right\rfloor$（基本段长度）

$r = n \bmod (t+1)$（需要分配额外一个学生的段数）

则：

有 $r$ 个段的长度为 $s+1$

有 $(t+1 - r)$ 个段的长度为 $s$

每个段产生的噪音和为该段的三角形数：

长度为 $L$ 的段产生的噪音和为 $\dfrac{L(L+1)}{2}$

因此，单栋楼的最小噪音和为：

${min\_noise}(n,t) = (t+1-r) \cdot \dfrac{s(s+1)}{2} + r \cdot \dfrac{(s+1)(s+2)}{2}$

其中： $s = \left\lfloor \dfrac{n}{t+1} \right\rfloor$, $r = n \bmod (t+1)$

3. 多栋楼的动态规划

定义状态：

$f[i][j]$：前 $i$ 栋楼使用 $j$ 次清空操作的最小总噪音

状态转移方程：

其中 $cnt[i]$ 表示第 $i$ 栋楼的学生总数。

初始条件：

$f[0][j] = 0$（没有楼时噪音为0）

最终答案：

$\min_{0 \le j \le K} f[M][j]$

算法复杂度

时间复杂度：$O(M \cdot K^2)$

外层循环：$M$ 栋楼

中层循环：$K$ 种清空次数

内层循环：最多 $K$ 次枚举分配方案

空间复杂度：$O(M \cdot K)$

存储动态规划状态表

总结

本题展示了组合优化问题的经典解法：

问题分解：将复杂的全局优化问题分解为独立的子问题

数学分析：通过数学推导得到子问题的闭式解，避免复杂的搜索过程

动态规划：使用DP框架将子问题的解组合成全局最优解

资源分配：核心是在多个竞争实体间分配有限的操作次数

这种"独立计算 + 资源分配"的模式适用于许多实际问题，如任务调度、资源分配、投资组合优化等。该解法在 $M \le 100$、$K \le 500$ 的约束下高效可行，体现了数学分析与算法设计的完美结合。