題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟣 CF626F. Group Projects

Problem Statement

題目簡述

有 nn 個學生，每個學生完成工作的時間為 AiA_i。需將學生分成若干組（可以一人一組）。
定義一個組的不平衡度 (imbalance) 為該組中最大的 AiA_i 減去最小的 AiA_i。
求有多少種分組方式，使得所有組的不平衡度總和不超過 kk。
答案對 109+710^9 + 7 取模。

Constraints

約束條件

  • 1≤n≤2001 \le n \le 200
  • 0≤k≤10000 \le k \le 1000
  • 1≤Ai≤5001 \le A_i \le 500

思路：動態規劃 (Open and Close Interval Trick)

本題和 CSES-1665 Coding Company 完全相同，請見 [解題紀錄]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
MOD = int(1e9 + 7)

def solve():
    n, V = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n

    A.sort()
    m = n >> 1  # 開啟的組數最多為 n/2

    f = [[0] * (V + 1) for _ in range(m + 1)]
    f[0][0] = 1
    for i, x in enumerate(A):
        nf = [[0] * (V + 1) for _ in range(m + 1)]
        d = x - (A[i - 1] if i > 0 else 0)
        for j in range(min(i + 1, m) + 1):
            cost = j * d
            for s in range(V - cost + 1):
                v = f[j][s] % MOD
                if not v: continue
                # 1. 開啟新組 (j -> j + 1)
                if j + 1 <= m: nf[j + 1][s + cost] += v
                # 2. 關閉舊組 (j -> j - 1)
                if j > 0: nf[j - 1][s + cost] += v * j
                # 3. 加入現有組或單獨一組 (j -> j)
                nf[j][s + cost] += v * (j + 1)
        f = nf
    print(sum(f[0]) % MOD)

if __name__ == '__main__':
    solve()

寫在最後

Cover Image Credit

The cover image was created by @崎白. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.