Solution

好题

不难发现一个性质，按 $g_i$ 从大到小排序，那么分到的饼干数也单调不升

排序后 $\texttt{DP}$，设 $f_{i,j}$ 表示考虑前 $i$ 个人，分了 $j$ 块饼干的最小怨气值之和

考虑如何转移，众所周知，单调不升的序列可以通过多个前缀相加组成

例如序列 $3,2,2,1$ 就可以由 $1$ 个 $[1,1]$ 前缀，$1$ 个 $[1,3]$ 前缀和 $1$ 个 $[1,4]$ 前缀组成

考虑枚举上一个前缀的位置 $k$（当前前缀就为 $[1,i]$），由于 $[1,k]$ 前缀都至少比 $[k+1,i]$ 多一个饼干，且 $[k+1,i]$ 分到的饼干数相同，那么对于 $[k+1,i]$ 的人，$a_i$ 就都等于 $k$，对答案的贡献就是 $(\sum_{o=k+1}^i a_o)\times k$，这里可以用前缀和优化，就是 $(s_i-s_k)\times k$

所以状态转移方程就是 $f_{i,j}=\min_{0\le k\le i} f_{k,j-i}+(s_i-s_k)\times k$，求方案也不难，转移过程中记录一下由哪个位置转移过来，再递归暴力加一下就行了

时间复杂度 $O(n^2m)$，注意 $\texttt{DP}$ 完还要按原来的顺序输出，因为 $\texttt{DP}$ 前进行了一次排序

怎么会有人看题解不点赞呢？

Code

#include<bits/stdc++.h>
using namespace std;
const int N=31,M=5001;
int n,m,s[N],ans[N],pre[N][M];
struct node {
    int x,id;
    bool operator <(node o)const {
        return x>o.x;
    }
}a[N];
long long f[N][M];

void solve(int x,int y)
{
    if (!x) return;
    for (int i=1;i<=x;i++) a[i].x++;
    solve(pre[x][y],y-x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i;
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i].x;
    memset(f,0x3f,sizeof f),f[0][0]=0;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=m;j++)
            for (int k=0,t;k<=i;k++)
                if ( (t=f[k][j-i]+1ll*(s[i]-s[k])*k)<f[i][j])
                    f[i][j]=t,pre[i][j]=k;

    printf("%lld\n",f[n][m]);
    for (int i=1;i<=n;i++) a[i].x=0; solve(n,m);
    for (int i=1;i<=n;i++) ans[a[i].id]=a[i].x;
    for (int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}