AcWing 277. 餅幹 (特殊的集合劃分方式）

​​AcWing 277. 餅幹​​

題目

有 m 塊餅幹分給 n 個人，要求每人至少分一塊。同時每一個人有一個怨氣值 a[i]，假設有 g[i] 個人比他分到的餅幹多，那麼這個人産生的怨氣就是 a[i] * g[i]。問最後怎麼配置設定餅幹使得怨氣值總和最小，輸出任意具體方案？

分析

所有配置設定方案的集合太大了。考慮縮小最優解集合。

首先肯定要配置設定的盡可能一樣，這樣就不會産生怨氣。如果不可避免的産生怨氣，那麼怨氣值高的配置設定的餅幹數也要高。

那麼集合變成了：“g[i] 大的配置設定的餅幹多” 的方案的集合。可以在這個集合上面做 dp。

首先将小朋友按 g[i] 從大到小排序。且配置設定的餅幹數量非嚴格遞減。

①：狀态表示

1. 集合： 表示給前 個小朋友配置設定
2. 屬性：方案怨氣值的最小值。

②：狀态轉移（集合劃分）

1. 0 個：
2. k 個 (k <= i)：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 30 + 5;
const int M = 5e3 + 5;

int n, m;
pii a[N];
int s[N], dp[N][M], ans[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    
    sort(a + 1, a + 1 + n, greater<pii>());
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i].first;
    memset(dp, INF, sizeof(dp));
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) {
            if (j < i) continue;    // 非法
            dp[i][j] = dp[i][j - i];
            for (int k = 1; k <= i && k <= j; k++) 
                dp[i][j] = min(dp[i][j], dp[i - k][j - k] + (i - k) * (s[i] - s[i - k]));
        }
        
    cout << dp[n][m] << "\n";
    int i = n, j = m, h = 0;    // 沿原路傳回，注意有兩種路徑
    while (i && j) {
        if (j >= i && dp[i][j] == dp[i][j - i]) j -= i, h++;
        else {
            for (int k = 1; k <= i && k <= j; k++) {
                if (dp[i][j] == dp[i - k][j - k] + (i - k) * (s[i] - s[i - k])){
                    for (int u = i; u > i - k; u--) 
                        ans[a[u].second] = 1 + h;
                    i -= k, j -= k;
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    puts("");
    return 0;
}