BZOJ 3174 [TJOI2013] 拯救小矮人：貪心排序+動態規劃（O(N²)）

題目：N 個矮人掉入深度 H 陷阱。矮人 i 身高 A_i（腳到肩），手臂長 B_i。搭人梯時，若 ΣA + B_k ≥ H，頂端矮人 k 可逃脫。逃脫者不再參與後續搭梯。求最多逃脫人數。N ≤ 2000。

貪心直覺與反例

直覺：A_i + B_i 越大逃脫能力越強，應讓能力弱的先逃。按 A_i+B_i 升序排序後貪心選擇。但純貪心失敗：當前矮人的 A_i 會疊加到後續矮人身上，影響其逃脫條件。

動態規劃修正

狀態定義：f[j] = 已逃脫 j 個矮人時，剩餘矮人身高總和 ΣA 的最大值。初始 f[0] = 0，其餘 -∞。

轉移：按 A_i+B_i 升序處理矮人 i。逆序更新 j（防重複使用）：

若 f[j] + B_i ≥ H - A_i  （即 f[j] + A_i + B_i ≥ H）
則 f[j+1] = max(f[j+1], f[j])   // 矮人i逃脫，不貢獻身高
否則
     f[j+1] = max(f[j+1], f[j] + A_i) // 矮人i留下搭梯，貢獻身高

答案：最大 j 使 f[j] ≥ 0（或最後更新時檢查 f[j+1] ≥ 0 即可增長答案）。

C++ 代碼

#include 
using namespace std;
const int MAXN = 2005;
int n, H, ans, f[MAXN];
struct Dwarf { int a, b; } d[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &d[i].a, &d[i].b);
    scanf("%d", &H);
    
    sort(d+1, d+n+1, [](const Dwarf& x, const Dwarf& y) {
        return x.a + x.b < y.a + y.b;
    });
    
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i-1; j >= 0; j--) {
            if (f[j] < 0) continue;
            if (f[j] + d[i].a + d[i].b >= H) {
                f[j+1] = max(f[j+1], f[j]); // 逃脫
            } else {
                f[j+1] = max(f[j+1], f[j] + d[i].a); // 留下
            }
        }
        if (f[ans+1] >= 0) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

樣例解析

樣例1:
2
20 10
5 5
30
輸出: 2
// 矮人2先逃: 5+5=10<30 留下; 矮人1逃: 5+20+10=35≥30; 矮人2再逃: 20+5=25<30? 
// 實際DP正確處理順序與狀態

樣例2:
H=35 輸出: 1

複雜度與優化

• 時間：O(N²)，N=2000 約 400 萬操作，極快。
• 空間：O(N) 一維 DP。
• 逆序更新 j 是 0/1 背包標準技巧，避免同一物品重複選取。