HDU 4381：區間塗色背包變體 - 最大白格數與最小操作數

題目大意

1~N 共 N 個格子，初始全黑。兩類操作：

1. 1 a x：在 [1, a] 中選 x 個黑格塗白。
2. 2 a x：在 [a, N] 中選 x 個黑格塗白。

區間黑格不足 x 則不能執行。求最多能塗多少白格，以及在達到最大白格時的最少操作數。N, M ≤ 1000。

解題思路

將問題轉化為分組背包：

• 類型 1 操作按 a 升序排序，代表從左向右塗色，每次塗最左邊的黑格。定義 dp1[j] 為塗滿前 j 個格子的最少操作數。轉移：dp1[j] = min(dp1[j], dp1[j - x] + 1)（逆序枚舉 j，0-1 背包）。
• 類型 2 操作對稱：將座標變換 a' = N+1-a，同樣按 a' 升序處理，得到 dp2[j] 為塗滿後 j 個格子的最少操作數。

最終枚舉總白格數 i = 1..N，左側塗 j 個，右側塗 i-j 個，若 dp1[j] + dp2[i-j] ≤ M 則可行。記錄最大 i 及對應最小操作數。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

struct Op { int pos, cnt; };

int main() {
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        int n, m; cin >> n >> m;
        vector L, R;
        for (int i = 0; i < m; ++i) {
            int s, a, x; cin >> s >> a >> x;
            if (s == 1) L.push_back({a, x});
            else R.push_back({n + 1 - a, x});
        }
        sort(L.begin(), L.end(), [](Op a, Op b){ return a.pos < b.pos; });
        sort(R.begin(), R.end(), [](Op a, Op b){ return a.pos < b.pos; });
        
        vector dp1(n+1, INF), dp2(n+1, INF);
        dp1[0] = dp2[0] = 0;
        for (auto &op : L)
            for (int j = n; j >= op.cnt; --j)
                dp1[j] = min(dp1[j], dp1[j - op.cnt] + 1);
        for (auto &op : R)
            for (int j = n; j >= op.cnt; --j)
                dp2[j] = min(dp2[j], dp2[j - op.cnt] + 1);
        
        int best = 0, minOps = 0;
        for (int i = 1; i <= n; ++i) {
            int curMin = INF;
            for (int j = 0; j <= i; ++j)
                curMin = min(curMin, dp1[j] + dp2[i - j]);
            if (curMin <= m) {
                best = i;
                minOps = curMin;
            }
        }
        cout << "Case " << tc << ": " << best << ' ' << minOps << '\n';
    }
    return 0;
}

關鍵點

• 操作順序固定（按邊界排序），等價於 0-1 背包選擇是否使用該操作。
• 左右對稱處理，最後枚舉分配方案。
• 複雜度 O(N·M)，滿足限制。