题目题解：A96792 小组项目分组 题意梳理 有 n 个学生，每个人耗时 ai ；将学生划分成若干小组； 一个小组的不平衡度 = 组内最大值−最小值；单人组不平衡度为 0； 所有小组不平衡度总和 ≤k，求分组方案总数，答案对 109+7 取模； 划分判定：只要有一对学生在一种分法同组、另一种分法不同组，就视作不同方案。 数据范围：n≤200, k≤1000。 核心前置结论（解题关键） 先排序：把数组 a 从小到大排序。设排序之后 a1 ≤a2 ≤a3 ⋯≤an 。当新增第 i 个学生放进一个包含 j 个人的连续组内时，这个组新增的不平衡贡献是：diff[i]=a[i]−a[i−1]如果当前组已有 j 个人，加入第 i 个人，该组增加 j×diff[i] 的总不平衡度。 原理：排序后，这一组里前面 j 个元素全部小于等于 a[i]，最大值变成 a[i]，整体不平衡度增加 j×(ai −ai−1 )。比如组内原来有 a1 ,a2 ，现在加入 a3 ：原来不平衡度：a2 −a1 ；新不平衡度：a3 −a1 ；差值为 (a3 −a1 )−(a2 −a1 )=1×(a3 −a2 )，此时 j=2（原来 2 个人），增量是 2×diff[3]。 DP 状态定义 dp[j][c]：处理完前面若干学生之后，最后一个组现在一共有 j 个人，已经累计花费总不平衡度为 c 的方案数目。这里只关注最后一组人数，前面的分组情况全部压缩在 DP 状态里面，这是经典的 “按连续划分” 的 DP 优化技巧。 状态转移（对应代码逻辑） 遍历第 i 个学生，生成新状态 ndp：对原来的状态 dp[j][c]，有 4 种选择： 将第 i 个人单独新建一组：最后一组人数变为 1，消耗不变；对应代码里 ndp[j+1][new_c] 其实是新建组逻辑； 把第 i 个人加入末尾当前的组：此时原来组内有 j 个人，新增代价 j×diff[i]； new_c=c+j×diff[i]，若 new_c>k 就跳过； 此时组内人数变成 j+1； 拆分组合：把末尾这一组拆开，原来组里 j 个人拿出一部分单独成组；这里代码里： ndp[j‑1][new_c] += 1LL * cur * j； ndp[j][new_c] +=1LL * cur * j；这两行对应组合计数：原来组里 j 个人，拆分的选择数是 j 种，对应不同划分方式，用来统计题目里不同分组方案。 为什么要乘 j：原来最后一组有 j 个人，在 j 个间隙里任选一个断开，就对应不同分组方案，所以方案数乘以 j。 DP 初始化与最终答案 初始化：，；代表刚开始没有学生或者第一个学生自成一组。 遍历完全部 n 个学生之后，把 dp[j][c]（j任意，0≤c≤k）全部累加起来就是答案。 样例 1 推演：输入n=3,k=2,a=[2,4,5] 排序之后数组：2,4,5；diff[1]=0, diff[2]=4−2=2, diff[3]=5−4=1； 依次处理 i=2（数值 4）、i=3（数值 5）； 最后统计所有总代价≤2的方案，得到答案 3，与样例输出一致。 代码逐段解读 const int MOD = 1e9+7;：模数，题目要求结果对 109+7取模； sort(a.begin(),a.end())：排序，整个 DP 成立的前提； diff[i]=a[i]-a[i-1]：计算相邻差值； dp[j][c]：状态定义如上； 内层循环： cur=dp[j][c]，取出原有方案数； new_c=c+j×diff[i]，判断是否超过 k； 分别处理：放入当前组、新建分组、拆分分组，同时1LL * cur * j强制 long long 防止 int 溢出； 最后循环累加所有 dp[∗][c]得到答案。 复杂度分析 n≤200, k≤1000；DP 状态：n×k，外层循环n次；总复杂度：O(n2k)；200×200×1000=4×107，在 1 秒时间限制内完全可以通过。 易错点说明 int 溢出问题：cur * j数值可能超过 int 范围，必须强制转为long long，代码里1LL * cur * j就是用来防止溢出； 排序必不可少，如果数组不排序，j×diff[i]的增量公式不再成立； 分组计数的核心：原来最后一组有 j 个人就对应 j 种拆分方式，所以方案数乘 j； 滚动数组：代码中每次用ndp覆盖旧的dp，节省空间。 思路精简总结 排序数组，将加入新元素带来的不平衡度简化为 j×diff[i]； DP 状态只保存最后一组人数和已经使用的不平衡开销； 分加入当前组、新建组、拆分组三种方式转移；拆分时乘 j统计分组方案； 最后累加所有总代价≤k 的方案即为答案。 代码：