CSES 🎯 CSES-1665 Coding Company

本題和 Codeforces 🟣 CF626F. Group Projects 完全相同。

🔗 CSES-1665 Coding Company

Problem Statement

題目簡述

有 $n$ 位工程師，每人有一個技術能力值 $t_i$。需要將他們分成若干個團隊。
每個團隊的懲罰值定義為該團隊中能力值最高與最低成員的差值，即 $max-min$；若團隊只有 $1$ 人，懲罰值為 $0$。
求有多少種分團隊方式，使得所有團隊的懲罰值總和不超過 $V$。答案需對 $10^9+7$ 取模。

Constraints

約束條件

• $1 \le n \le 100$
• $0 \le V \le 5000$
• $0 \le t_i \le 100$

---

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

Open and Close Interval Trick

[Tutorial] Non-trivial DP Tricks and Techniques

這題是典型的「排序後按貢獻計算區間端點」DP。難點不在於某個團隊的懲罰值怎麼算，而在於：分組方式太多，不能真的把每個團隊都枚舉出來。

先看直接做法。若枚舉每一種分組，再逐一計算所有團隊的懲罰值，分支數會隨人數快速爆炸，對 $n=100$ 完全不可行。因此需要換一種統計方式。

1. 轉換貢獻計算方式

不妨先把能力值排序。對某個團隊，假設其中成員能力值為
$s_1 \le s_2 \le \dots \le s_m$，它的懲罰值是最大值減最小值：

$$s_m-s_1.$$

把這個差值拆成相鄰差值之和：

$$s_m-s_1=(s_2-s_1)+(s_3-s_2)+\cdots+(s_m-s_{m-1}).$$

關鍵觀察

排序後，每一段相鄰能力值差，只會貢獻給那些「已經選了團隊最小值，但還沒選到團隊最大值」的團隊。換句話說，當我們從小到大掃描時，只要知道目前有多少個尚未關閉的團隊，就知道下一段差值會被加幾次。

這就是 Open and Close Interval Trick：把一個團隊看成排序序列上的一段開閉過程。遇到團隊最小值時開啟，遇到團隊最大值時關閉；中間的相鄰差值，都會被這個團隊跨過並貢獻一次。

可復用模型

只要一題的代價長得像「每組最大值減最小值」，並且元素可以排序，就可以優先想：把最大最小差拆成相鄰差值，再用目前開啟的組數計算貢獻。

2. 動態規劃狀態定義

掃描到某個位置時，真正需要保留的資訊只有兩件事：

1. 目前還有多少個團隊已開啟但未關閉。
2. 目前累積的懲罰值總和是多少。

因此先寫出完整狀態：

$$dp[i][j][s]$$

表示處理完排序後前 $i$ 位工程師後，目前有 $j$ 個團隊已開啟但尚未關閉，且累積懲罰值總和為 $s$ 的分組方案數。

其中：

• $i$ 表示已處理的人數。
• $j$ 表示目前開啟中的團隊數。
• $s$ 表示目前累積的懲罰值總和，且只需要考慮 $0\le s\le V$。

開啟團隊數還可以進一步限制。任何時刻，開啟中的團隊必須在之後被某個工程師關閉，所以它不能超過剩餘未處理的人數；同時它也不可能超過已處理的人數。因此只需要考慮：

$$j\le \min(i,n-i)\le \left\lfloor\frac n2\right\rfloor.$$

這能把開啟團隊數這一維從 $n$ 壓到 $\lfloor n/2\rfloor$。

初始狀態為：

$$dp[0][0][0]=1.$$

一開始還沒有處理任何工程師，也沒有開啟中的團隊，累積懲罰值為 $0$，這是一種合法空方案。

最後答案要求所有團隊都已關閉，所以是：

$$\sum_{s=0}^{V} dp[n][0][s].$$

也就是處理完所有工程師後，開啟團隊數為 $0$，且總懲罰值不超過 $V$ 的所有方案數。

由於第 $i$ 層只會從第 $i-1$ 層轉移而來，實作時用滾動陣列即可，不需要保留完整三維 DP。也就是把目前層寫成 $f[j][s]$，下一層寫成 $nf[j][s]$，含義仍然是「開啟團隊數為 $j$、累積代價為 $s$ 的方案數」。

3. 狀態轉移：Open and Close Interval Trick

處理下一位工程師前，先看目前能力值與前一個能力值的差。若現在有 $j$ 個開啟中的團隊，這段差值會被這 $j$ 個團隊全部跨過，所以累積代價需要增加：

$$j \times \text{相鄰差值}.$$

如果增加後已經超過上限，這個狀態就不能繼續轉移。

為了把轉移式寫清楚，令目前狀態為 $f[j][s]$，表示處理到上一個位置後，有 $j$ 個團隊仍然開啟，累積懲罰值為 $s$ 的方案數。

處理目前位置時，先加入相鄰差值帶來的貢獻。設

$$c=s+j\times \text{相鄰差值}.$$

若 $c>V$，這個狀態無效；否則把方案轉移到下一層狀態 $nf$。

接下來考慮目前工程師在某個團隊中的角色，有四種情況：

1. 開啟一個新組 ($j \to j+1$)：

   • 目前工程師作為某個團隊的最小值。
   • 沒有選擇哪個舊團隊的問題，所以係數是 $1$。

     $$nf[j+1][c] \mathrel{+}= f[j][s]$$

2. 關閉一個舊組 ($j \to j-1$)：

   • 目前工程師作為某個已開啟團隊的最大值。
   • 可以選擇 $j$ 個開啟團隊中的任意一個關閉，所以係數是 $j$。

     $$nf[j-1][c] \mathrel{+}= j\cdot f[j][s]$$

3. 加入一個舊組 ($j \to j$)：

   • 目前工程師既不是最小值，也不是最大值，只是放入某個已開啟團隊中。
   • 有 $j$ 個團隊可選，所以係數是 $j$。

     $$nf[j][c] \mathrel{+}= j\cdot f[j][s]$$

4. 單獨自成一組 ($j \to j$)：

   • 目前工程師同時是最小值和最大值。
   • 相當於開啟後立刻關閉，係數是 $1$。

     $$nf[j][c] \mathrel{+}= f[j][s]$$

其中第 3、4 種都不改變開啟團隊數，可以合併成：

$$nf[j][c] \mathrel{+}= (j+1)\cdot f[j][s].$$

這也是程式裡同一層狀態轉移乘上 $j+1$ 的來源。

整理成完整轉移式，就是：

$$\begin{aligned} nf[j+1][c] &\mathrel{+}= f[j][s] && \text{開啟新組},\\ nf[j-1][c] &\mathrel{+}= j\cdot f[j][s] && \text{關閉舊組},\\ nf[j][c] &\mathrel{+}= (j+1)\cdot f[j][s] && \text{加入舊組或單獨成組}. \end{aligned}$$

實作時再檢查 $j+1$ 是否超過開啟組數上界，以及 $j>0$ 時才允許關閉舊組。

正確性直覺

每位工程師在排序後只會被處理一次，而它對分組的角色只可能是開啟、關閉、加入、單獨成組四種之一。另一方面，每個合法分組也能唯一對應到這些開閉操作。因此 DP 既不漏算，也不重算。

易錯點

相鄰差值的貢獻要在決定目前工程師角色之前加入，因為這段距離是「前一個能力值到目前能力值」之間，被先前已開啟、尚未關閉的團隊跨過。

複雜度分析

• 時間複雜度：$\mathcal{O}(n^2V)$。共有 $n$ 個位置，開啟團隊數最多 $\lfloor n/2\rfloor$，累積代價最多 $V$。
• 空間複雜度：$\mathcal{O}(nV)$。使用滾動陣列後，只保留「開啟團隊數 $\times$ 累積代價」兩維狀態。

---

Code

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.