题目分析
比较巧妙的转化，但是输出方案的时候出了问题，迫使我看了y总的输出方案代码……不知道自己的为啥不行，放坑了
首先一个性质：贪婪度越大的孩子获得的饼干数应该越多。证明也不难证，直接用贪心中的临项交换法就行了，不再赘述。因此我们可以把小朋友按照贪婪值从大到小排序，这样之后他们分配到的饼干数量是单调递减的。
状态设计：设 (f_{i,j}) 表示前 (i) 个小朋友分了 (j) 块饼干所得到的最小怨气值总和。
状态转移：
- 如果第 (i) 个小朋友获得的饼干数不为 (1) 且 (j>=i)，那么 (f_{i,j}) 的一个可行选择为 (f_{i,j-i})，这两个式子是等价的，前 (i) 个小朋友分了 (j) 块饼干等价于前 (i) 个小朋友分了 (j-i) 块饼干，原因是这样相当于每个人少拿一块饼干，但是获得的饼干数量的相对顺序是不变的，所以怨气值之和也是不会变的。
- 如果第 (i) 个小朋友获得的饼干数为 (1)，那么就可以枚举前面有多少个小朋友获得的饼干数为 (1)，从中取最小值，这一步可以用前缀和优化。
由此可得整个DP的转移方程为：
[f_{i,j}=minegin{cases}f_{i,j-i}& ext{if } jge i\minlimits_{k=0}^{i-1}(f_{k,j-(i-k)}+k imessumlimits_{x=k+1}^{i}g_x)& ext{if }jge(i-k)end{cases}
]
初始条件为 (f_{0,0}=0)，最终目标为 (f_{n,m})。
输出方案有点迷……
代码
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define pii pair <int, int>
using namespace std;
const int A = 33;
const int B = 5011;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
pii g[A];
int n, m, f[A][B], sum[A], ans[A];
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
g[i].first = read();
g[i].second = i;
}
sort(g + 1, g + 1 + n);
reverse(g + 1, g + 1 + n);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + g[i].first;
memset(f, inf, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= i) f[i][j] = f[i][j - i];
for (int k = 0; k < i && j >= (i - k); k++)
f[i][j] = min(f[i][j], f[k][j - (i - k)] + k * (sum[i] - sum[k]));
}
}
cout << f[n][m] << '
';
int i = n, j = m, h = 0;
while (i && j) {
if (j >= i && f[i][j] == f[i][j - i]) j -= i, h++;
else {
for (int k = 1; k <= i && k <= j; k++) {
if (f[i][j] == f[i - k][j - k] + (i - k) * (sum[i] - sum[i - k])) {
for (int x = i; x > i - k; x--) ans[g[x].second] = 1 + h;
i -= k, j -= k;
break;
}
}
}
}
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
puts("");
return 0;
}