Codeforces 417D Cunning Gena：狀態壓縮 DP + 監視器成本優化

問題建模

Gena 有 n 個朋友 (n≤100)，m 道題 (m≤20)，單台顯示器價格 b。第 i 個朋友：解題費用 x_i，需至少 k_i 台顯示器，能解決 m_i 道特定題目。目標：最小化總成本（朋友費用 + 顯示器費用）解決所有 m 道題。初始無顯示器。

關鍵觀察：按 k_i 排序

若按所需顯示器數 k_i 升序處理朋友，當考慮第 i 個朋友時，之前所有朋友的 k_j ≤ k_i。若當前方案已購買 ≥ k_i 台顯示器，後續朋友的顯示器需求自動滿足，無需額外購買。因此只需在 DP 中記錄「已解決題目集合」，顯示器成本在轉移時一次性結算。

狀態定義

• dp[mask]：解決題目集合 mask 的最小朋友費用（不含顯示器）
• 初始 dp[0]=0，其餘 INF
• 按 k_i 升序遍歷朋友，狀態壓縮轉移：dp[mask | skill_i] = min(dp[mask | skill_i], dp[mask] + x_i)
• 每步更新答案：ans = min(ans, dp[full] + k_i * b)

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const long long INF = 1e18;
struct Friend { int cost, k, mask; } f[110];
long long dp[1<<20];

bool cmp(Friend a, Friend b) { return a.k < b.k; }

int main() {
    int n, m, b; scanf("%d%d%d", &n, &m, &b);
    for (int i=0; i=0; mask--) if (dp[mask] != INF) {
            int nmask = mask | f[i].mask;
            dp[nmask] = min(dp[nmask], dp[mask] + f[i].cost);
        }
        if (dp[full] != INF) ans = min(ans, dp[full] + 1LL * f[i].k * b);
    }
    printf("%lld\n", ans==INF ? -1 : ans);
    return 0;
}

樣例驗證

輸入1:
2 2 1
100 1 1
2
100 2 1
1
輸出: 202
// 兩朋友各買1台顯示器，共200 + 2*1 = 202

輸入2:
3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2
輸出: 205
// 前兩朋友各解一題，共200 + 1*5 = 205

輸入3:
1 2 1
1 1 1
1
輸出: -1
// 無法覆蓋題2

複雜度

• 狀態數：2^m ≤ 2^20 ≈ 10^6
• 轉移：n × 2^m ≤ 10^8，邊界較緊但可行（逆序遍歷避免重複更新）
• 排序：O(n log n)