WUST OJ 1421 We Love Girl：貪心/DP 分配男女接待員最大化滿意度

題目大意

n 所學校 (≤20)，x 名女生、y 名男生 (x+y=n)。第 i 校派女生得 pᵢ 滿意度，派男生得 qᵢ。每校必須分配一名接待員 (男或女)，求最大總滿意度。

方法一：貪心 (差值排序)

對每校計算 diff = |pᵢ - qᵢ|，降序排序。依序處理：若 pᵢ > qᵢ 且還有女生名額，派女生；否則派男生 (若有名額)；名額用盡則強制派另一性別。
正確性：差值大的學校「選錯」損失大，優先滿足其最優選擇屬局部最優推導全局最優 (交換論證)。

方法二：動態規劃 (0/1 背包變體)

dp[i][j] = 前 i 校選 j 名女生的最大滿意度。
轉移：dp[i][j] = max(dp[i-1][j] + qᵢ, dp[i-1][j-1] + pᵢ) (j>0)。
答案：max(dp[n][j]) for j=0..x (且 n-j ≤ y)。
複雜度 O(n·x)，n≤20 極小，DP 絕對正確且易寫。

完整程式碼 (雙版本)

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, x, y; cin >> n >> x >> y;
        vector p(n+1), q(n+1);
        for (int i=1;i<=n;++i) cin >> p[i] >> q[i];
        x = min(x, n); // 防 x>n
        y = min(y, n);

        // --- DP 版 (推薦，絕對正確) ---
        const int INF = 0x3f3f3f3f;
        vector> dp(n+1, vector(x+1, -INF));
        dp[0][0] = 0;
        for (int i=1;i<=n;++i) {
            for (int j=0;j<=x;++j) {
                // 選男生
                if (i-j <= y) dp[i][j] = max(dp[i][j], dp[i-1][j] + q[i]);
                // 選女生
                if (j>0 && i-j <= y) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + p[i]);
            }
        }
        int ans = 0;
        for (int j=0;j<=x;++j) ans = max(ans, dp[n][j]);
        cout << ans << '\n';
    }
    return 0;
}

貪心版 (供參考)

struct School { int p, q, diff; };
// ... 輸入 ...
vector a(n);
for (int i=0;i B.diff; });
int ans=0, gx=x, by=y;
for (auto& s : a) {
    if (s.p > s.q) {
        if (gx) { ans+=s.p; --gx; }
        else { ans+=s.q; --by; }
    } else {
        if (by) { ans+=s.q; --by; }
        else { ans+=s.p; --gx; }
    }
}
cout << ans << '\n';

複雜度對比

總結

小規模 (n≤20) 分配問題，DP 是「想不到貪心證明時的保底寫法」，狀態定義清晰、轉移直觀，強烈推薦面試/比賽優先使用。