Codeforces 🔵 CF466D. Increase Sequence

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

🔗 🔵 CF466D. Increase Sequence

Problem Statement

題目簡述

給定長度為 $n$ 的整數序列與目標高度 $h$。
一次操作可以選擇一段連續區間，將區間內所有元素加 $1$。
所有被選區間的左端點必須兩兩不同，右端點也必須兩兩不同。
求有多少種操作方案可以讓所有元素最後都等於 $h$，答案對 $10^9+7$ 取模。

Constraints

約束條件

• $1 \le n \le 2000$
• $1 \le h \le 2000$
• $0 \le A_i \le 2000$
• 所有輸入皆為整數

---

思路：把補高度轉成區間覆蓋

先把「加區間」換個角度看。令

$$B_i = h - A_i$$

則 $B_i$ 代表第 $i$ 個位置還需要被多少個操作區間覆蓋。換句話說，當我們從左到右掃描到位置 $i$ 時，必須剛好有 $B_i$ 個區間覆蓋住位置 $i$。

如果存在 $B_i < 0$，表示原本高度已經超過 $h$，無論如何都不能靠加法降回來，答案直接是 $0$。否則，問題就變成：構造若干區間，使第 $i$ 個位置剛好被覆蓋 $B_i$ 次，且每個位置最多當一次左端點、最多當一次右端點。

右端點不是堆疊配對

這裡雖然可以用左右括號想像區間開閉，但結束一個區間時，不需要和最近開啟的區間配對。
只要右端點位置不同，就能從所有尚未結束的區間中任選一個結束，因此減少覆蓋數時的貢獻是目前開啟數量，而不是固定 $1$。

方法一：差分陣列與組合數學

為了處理邊界，令 $B_0 = B_{n+1} = 0$。從左到右觀察相鄰兩個位置的需求差異

$$B_i - B_{i-1}$$

由於每個位置最多只能作為一次左端點、一次右端點，所以從 $i-1$ 走到 $i$ 時，覆蓋數最多增加 $1$；從 $i$ 走到下一個位置時，覆蓋數最多減少 $1$。也就是說，相鄰兩項的差值只能是 $-1,0,1$，否則不可能用合法區間構造出來。

當我們從 $i-1$ 移動到 $i$ 時，可以分成以下四種情況討論：

1. $B_i = B_{i-1}+1$

   位置 $i$ 比前一個位置多需要一層覆蓋。由於前一個位置不需要這一層，而目前位置需要，這一層只能來自一個從 $i$ 開始的新區間。

   又因為每個位置最多只能作為一次左端點，所以這裡必須開啟新區間，方案數貢獻為 $1$。

2. $B_i = B_{i-1}-1$

   位置 $i$ 比前一個位置少需要一層覆蓋，表示有一個區間覆蓋了 $i-1$，但不再覆蓋 $i$，也就是它在 $i-1$ 結束。

   在位置 $i-1$ 時共有 $B_{i-1}$ 個區間仍然開啟，可以任選其中一個結束，因此方案數貢獻為 $B_{i-1}$。

3. $B_i = B_{i-1}$

   覆蓋數不變，有兩種可能：

   • 什麼都不做，沒有區間在這裡開始或結束，貢獻 $1$。
   • 關閉一個舊區間，並在位置 $i$ 開啟一個新區間。此時可從 $B_{i-1}$ 個已開啟區間中任選一個結束，貢獻 $B_{i-1}$。

   所以總貢獻為 $B_{i-1}+1$。

4. $|B_i-B_{i-1}|>1$

   變化量超過 $1$，但單一位置最多只能新增一個左端點、移除一個右端點，無法讓覆蓋數一次跳這麼多。

   因此這種情況不合法，答案為 $0$。

把每一步的合法選擇數相乘，就是總方案數。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$，只需掃描一次覆蓋需求。
• 空間複雜度：$\mathcal{O}(n)$。

方法二：Open and Close Interval Trick

另一種寫法是把區間看成從左往右逐步「開啟」與「關閉」。掃描到位置 $i$ 時，必須剛好有 $B_i$ 個區間覆蓋住它；掃描完位置 $i$ 後，我們只需要知道還有多少區間會繼續覆蓋下一個位置。

狀態定義

令 $f[i][j]$ 表示處理完前 $i$ 個位置後，仍然有 $j$ 個區間處於開啟狀態，也就是會繼續覆蓋位置 $i+1$ 的方案數。

初始狀態為 $f[0][0]=1$，表示還沒處理任何位置時，沒有任何區間開啟。

狀態轉移

考慮位置 $i$。假設處理位置 $i$ 之前，已經有 $j$ 個區間處於開啟狀態，也就是這些區間原本就會覆蓋位置 $i$。接著從這個舊狀態往下一層更新，可以分成五種操作形態：

1. 不開不關

   已有的 $j$ 個區間直接通過目前位置，處理完後仍留下 $j$ 個開啟區間，覆蓋數為 $j$。

   因此需要 $j=B_i$，轉移為：

   $$f[i][j] \leftarrow f[i][j] + f[i-1][j]$$

2. 開啟一個新區間

   新區間從位置 $i$ 開始，並會繼續傳到下一位。原本有 $j$ 個區間開啟，處理完後留下 $j+1$ 個開啟區間。

   目前位置被 $j+1$ 個區間覆蓋，因此需要 $j+1=B_i$，轉移為：

   $$f[i][j+1] \leftarrow f[i][j+1] + f[i-1][j]$$

3. 關閉一個舊區間

   有一個舊區間在位置 $i$ 結束。它仍然覆蓋目前位置，但不會傳到下一位。

   原本有 $j$ 個區間開啟，目前位置被 $j$ 個區間覆蓋，所以需要 $j=B_i$。結束時要從這 $j$ 個舊區間中選一個，處理完後留下 $j-1$ 個開啟區間，轉移為：

   $$f[i][j-1] \leftarrow f[i][j-1] + f[i-1][j]\cdot j$$

4. 開啟並立即關閉

   在位置 $i$ 放一個長度為 $1$ 的區間。這個新區間覆蓋目前位置，但不會留下來。

   處理前後的開啟區間數都為 $j$，目前位置實際被 $j+1$ 個區間覆蓋，所以需要 $j+1=B_i$，轉移為：

   $$f[i][j] \leftarrow f[i][j] + f[i-1][j]$$

5. 關閉一個舊區間，同時開啟一個新區間

   有一個舊區間在位置 $i$ 結束，同時有一個新區間從位置 $i$ 開始。處理前後留下的開啟區間數都為 $j$。

   目前位置被「原本 $j$ 個舊區間」加上「新開的一個區間」覆蓋，所以需要 $j+1=B_i$。關閉的舊區間可以從原本 $j$ 個開啟區間中選一個，轉移為：

   $$f[i][j] \leftarrow f[i][j] + f[i-1][j]\cdot j$$

為什麼每步只有常數個狀態

固定目前位置後，合法的留下數只有兩種：

• 若目前位置沒有額外結束的區間，留下的開啟數必須是 $B_i$。
• 若目前位置有一個區間結束，或有一個長度為 $1$ 的區間，留下的開啟數必須是 $B_i-1$。

因此不需要真的維護整張二維 DP 表，只需要保留可能出現的狀態即可。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$，每個位置只會更新常數個可能狀態。
• 空間複雜度：$\mathcal{O}(1)$，滾動字典中有效狀態數為常數級。

---

Code

方法一：差分陣列

from itertools import pairwise

MOD = int(1e9 + 7)

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

    B = [0] + [h - x for x in A] + [0]
    if any(x < 0 for x in B):
        print(0)
        return
    
    ans = 1
    for x, y in pairwise(B):
        diff = y - x
        if diff == 1:
            # 需要增加一個覆蓋數 -> 必須開啟一個新區間，有 1 種選法
            ans = (ans * 1)
        elif diff == -1:
            # 需要減少一個覆蓋數 -> 必須關閉一個舊區間
            # 有 x 個正在進行的區間，可以選任意一個關閉
            ans = (ans * x) % MOD
        elif diff == 0:
            # 覆蓋數不變
            # 選項 1: 什麼都不做，有 1 種選法
            # 選項 2: 關閉一個舊的，開啟一個新的，有 x 種選法
            ans = (ans * (x + 1)) % MOD
        else:
            print(0)
            return
    print(ans)

if __name__ == "__main__":
    solve()

方法二：動態規劃

from collections import defaultdict

MOD = int(1e9 + 7)

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

    if any(x > h for x in A):
        print(0)
        return

    # f[i][j] 表示考慮前 i 個數字後，還有 j 個區間處於「開啟」狀態的方案數。
    f = defaultdict(int)
    f[0] = 1
    for x in A:
        nf = defaultdict(int)
        need = h - x

        for j, ways in f.items():
            if ways == 0:
                continue

            # 1. 不操作：j 個區間通過目前位置。
            if j == need:
                nf[j] = (nf[j] + ways) % MOD

            # 2. 開啟一個新區間：覆蓋數變成 j + 1。
            if j + 1 == need:
                nf[j + 1] = (nf[j + 1] + ways) % MOD

            # 3. 關閉一個舊區間：j 個舊區間覆蓋目前位置，選一個結束。
            if j == need and j > 0:
                nf[j - 1] = (nf[j - 1] + ways * j) % MOD

            # 4. 開啟並立即關閉：多一個長度為 1 的區間覆蓋目前位置。
            if j + 1 == need:
                nf[j] = (nf[j] + ways) % MOD

            # 5. 關閉一個舊區間，同時開啟一個新區間。
            if j + 1 == need and j > 0:
                nf[j] = (nf[j] + ways * j) % MOD

        f = nf

    print(f[0])


if __name__ == "__main__":
    solve()