思路分析

本题首先需要知道贪心的思路，也就是怨气值大的分得的饼干一定多，因为这样饼干比他多的人就少，这样就可以保证总的怨气值最小，知道这个之后，我们可以按照怨气值从大到小排序，这样从前到后每个人的分配的饼干就一定是非严格递减的，然后我们可以按照一种新的dp方式，首先可以把处理的前i个同学的作为阶段，把分配的饼干个数作为附加维度，然后按照末尾的连续的同学有多少个人分配到一块饼干进行状态计算，如下：

参考文献：

https://www.acwing.com/solution/AcWing/content/5240/

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 35, M = 5010;

pair<int, int> g[N];
int dp[N][M];
int sum[N];
int n, m;

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;++i){
        cin >> g[i].first;
        g[i].second = i;
    }
    //排序保证 从前到后每个小朋友分配到的饼干递减（非严格）
    sort(g+1, g+1+n, [](auto& a, auto& b){
        return a.first > b.first;
    });
    for(int i = 1;i <= n;++i) sum[i] = sum[i-1] + g[i].first;

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;

    for(int i = 1;i <= n;++i)
        for(int j = i;j <= m;++j){
            dp[i][j] = dp[i][j-i];//末尾有0个连续的1
            for(int k = 1;k <= i && k <= j;++k)//有k个连续的1
                dp[i][j] = min(dp[i][j], dp[i-k][j-k] + (sum[i] - sum[i-k])*(i-k));   
        }

    cout << dp[n][m] << endl;

    int ans[N];
    int i = n, j = m;
    int h = 0;//代表所有的人的饼干减了h
    while(j && i && j >= i){
        if(dp[i][j] == dp[i][j-i]) {
            ++h;
            j -= i;
        }
        else
            for(int k = 1;k <= i && k <= j;++k)
                if(dp[i][j] == dp[i-k][j-k] + (sum[i] - sum[i-k])*(i-k)){
                    for(int t = i;t >= i-k;--t)
                        ans[g[t].second] = h + 1;
                    j -= k;
                    i -= k;
                    break;
                }
    }

    for(int i = 1;i <= n;++i) cout << ans[i] << " ";

    return 0;
}