F. Group Projects 题解

题目描述

有 $n$ 个学生，第 $i$ 个学生完成工作需要 $a_i$ 分钟。将学生分成若干组（允许单人一组），定义一组的不平衡度为组内最大 $a_i$ 减去最小 $a_i$。求所有组的不平衡度之和不超过 $k$ 的分组方案数。答案对 $10^9+7$ 取模。

• $1 \le n \le 200$，$0 \le k \le 1000$，$1 \le a_i \le 500$

算法思路

这是一个动态规划问题。关键观察：总不平衡度只与每组的最小值和最大值有关，且可以转化为相邻学生差值乘以覆盖该差值的区间数之和。

1. 排序与差分思想

将 $a$ 从小到大排序，记 $b[1..n]$ 为排序后的数组。设 $b[0]=b[1]$。考虑相邻两个学生的时间差 $d_i = b[i] - b[i-1]$（$i \ge 1$）。对于任意一个分组，若一个组包含了 $b[l..r]$，则该组的不平衡度贡献为 $b[r]-b[l] = \sum_{i=l+1}^{r} d_i$。因此总不平衡度等于所有 $d_i$ 乘以“覆盖该 $d_i$ 的组的个数”之和。

2. 动态规划状态定义

我们按排序后的顺序依次处理每个学生。定义状态：

• $i$：已经处理了前 $i$ 个学生（$0 \le i \le n$）。
• $j$：当前开放的组的数量。一个组在遇到它的最小值时“打开”，在遇到最大值时“关闭”。开放组意味着已经确定了最小值，但尚未确定最大值，未来可以加入更多学生。
• $k$：当前已经产生的总不平衡度（只计算已经关闭的组和部分开放的组已经确定的增量）。

转移时，当我们从第 $i$ 个学生走向第 $i+1$ 个学生时，所有开放的组都会因为时间差 $d_{i+1}=b[i+1]-b[i]$ 而增加不平衡度。因此，在考虑第 $i+1$ 个学生的选择之前，先更新 $k \leftarrow k + j \cdot d_{i+1}$。如果新 $k > K$ 则剪枝。

3. 四种转移

对于第 $i+1$ 个学生，有四种互斥的选择：

1. 自成一派：自己单独成组，不改变开放组数量 $j$。
   $dp[i+1][j][newk] += dp[i][j][k]$

2. 新开一个组：作为某个新组的最小值，开放组数量加 $1$。
   $dp[i+1][j+1][newk] += dp[i][j][k]$

3. 加入一个现有开放组：成为某个开放组的中间成员（非最小值也非最大值），不改变 $j$。有 $j$ 种选择。
   $dp[i+1][j][newk] += dp[i][j][k] * j$

4. 关闭一个开放组：成为某个开放组的最大值，结束该组，开放组数量减 $1$。有 $j$ 种选择。
   $dp[i+1][j-1][newk] += dp[i][j][k] * j$

4. 初始与答案

• 初始：$dp[0][0][0] = 1$。
• 最终答案：处理完所有 $n$ 个学生后，所有组必须关闭（$j=0$），对 $k \le K$ 求和：$\sum_{k=0}^{K} dp[n][0][k]$。

5. 优化

• 使用滚动数组，空间复杂度 $O(nK)$。
• 时间复杂度 $O(n^2 K)$，在 $n=200, K=1000$ 时可接受（约 $4\times10^7$ 次运算）。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 205;
const int MAXK = 1005;

int n, K;
int a[MAXN];
ll dp[2][MAXN][MAXK];

int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    a[0] = a[1];

    dp[0][0][0] = 1;

    for (int i = 0; i < n; i++) {
        int cur = i & 1, nxt = cur ^ 1;
        memset(dp[nxt], 0, sizeof(dp[nxt]));

        int delta = a[i + 1] - a[i];
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= K; k++) {
                ll val = dp[cur][j][k];
                if (!val) continue;
                int newk = k + j * delta;
                if (newk > K) continue;

                // 1. 自成一派
                dp[nxt][j][newk] = (dp[nxt][j][newk] + val) % MOD;
                // 2. 新开一组
                dp[nxt][j + 1][newk] = (dp[nxt][j + 1][newk] + val) % MOD;
                if (j > 0) {
                    // 3. 加入一个现有组
                    dp[nxt][j][newk] = (dp[nxt][j][newk] + val * j) % MOD;
                    // 4. 关闭一个组
                    dp[nxt][j - 1][newk] = (dp[nxt][j - 1][newk] + val * j) % MOD;
                }
            }
        }
    }

    ll ans = 0;
    for (int k = 0; k <= K; k++) ans = (ans + dp[n & 1][0][k]) % MOD;
    printf("%lld\n", ans);
    return 0;
}