「CH 5105」Cookies (DP + 输出方案)

CH 5105
题意：有$n$个人，每个人有一个$g_i$，现给$n$人分配$m$个饼干(每个人都要有饼干)，对于第$i$个人，比他饼干多的人数记为$a_i$，请最小化$\sum_{i=1}^n a_i g_i$

容易发现$g_i$大的$a_i$尽可能小，所以$g_i$单调递减时分配的饼干也单调递减。
对$g$降序排序后，设$dp(i,j)$为前$i$个人合分$j$块饼干的最小值。
则有
$$
dp(i,j)=min(dp(i,j-i), min_{0 \leq k < i}(dp(k, j - (i - k)) + k \cdot \sum_{x=k+1}^ig(x)))
$$

当第$i$位不填$1$时，前$i$个人分$j$块对应于前$i$个人分$j-i$块，因为每个人少拿一块，相对关系不变
否则，枚举前面有几个和它一样的，统计答案。

注意解的输出要按照dp意义来，注意递归输出在本题会好用些。

知识点：
1、DP 输出方案要按照dp意义来。并且有时候递归输出方便。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int INF = 1000000000;

    struct data {
        int g, id;
    } c[35];

    int n, m, dp[35][5005], pre[35][5005][2], sum[35], ans[35];

    bool cmp(data a, data b) {return a.g > b.g;}

    void print(int x, int y) {
        if (x == 0 || y == 0) return ;
        print(pre[x][y][0], pre[x][y][1]);
        if (pre[x][y][0] == x) {
            for (int i = 1; i <= x; ++i) ++ans[c[i].id];
        } else for (int i = pre[x][y][0] + 1; i <= x; ++i) ans[c[i].id] = 1;
    }

    void clean() {
        ms(pre, -1), ms(ans, 0);
    }
    int solve() {
        clean();
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) cin >> c[i].g, c[i].id = i;
        sort(c + 1, c + 1 + n, cmp);
        sum[0] = 0;
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + c[i].g;
        for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j) dp[i][j] = INF;
        dp[0][0] = 0;
        for (int i = 0; i <= n; ++i) {
            for (int j = i; j <= m; ++j) {
                if (dp[i][j - i] < dp[i][j]) 
                    dp[i][j] = dp[i][j - i], pre[i][j][0] = i, pre[i][j][1] = j - i;
                for (int k = 0; k < i; ++k) {
                    if (dp[k][j - (i - k)] + k * (sum[i] - sum[k]) < dp[i][j]) 
                        dp[i][j] = dp[k][j - (i - k)] + k * (sum[i] - sum[k]), pre[i][j][0] = k, pre[i][j][1] = j - (i - k);
                }
            }
        }
        printf("%d\n", dp[n][m]);
        print(n, m);
        for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}