思路
我们先看一下本题的主要思想:先用贪心把最优解缩小到某个较小的范围内,再去用 $DP$ 找到最优解。
显然,根据排序不等式,把所有小朋友按照 $g[i]$ 从大到小排序,排名靠前的小朋友要分到更多的饼干。
然后我们就进行 $DP$。
状态表示 $(f_{i,j})$:
- 集合:$f_{i,j}$ 表示所有将 $j$ 个饼干分配给前 $i$ 个小朋友,一定要保证分配单位饼干单调下降的所有方案构成的集合。
- 属性:最低怨气值总和
状态计算:
我们以最后有 $k$ 个小朋友分配 $1$ 个饼干为划分依据,进行转移。分类讨论:
- $k=0$,则答案为 $f_{i, j - i}$。
- $k\ne 0$,则答案为 $f_{i - k, j - k} + (sum[i] - sum[i - k]) * (i - k)$,其中 $sum$ 数组表示怨气值的前缀和。
最后顺藤摸瓜的寻找答案即可。
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 40, M = 5010;
int n, m;
PII g[N];
int sum[N], f[N][M], ans[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
cin >> g[i].x;
g[i].y = i;
}
sort(g + 1, g + n + 1);
reverse(g + 1, g + n + 1);
for (int i = 1; i <= n; i ++ )
sum[i] = sum[i - 1] + g[i].x;
memset(f, 0x3f, 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 = 1; k <= min(i, j); k ++ )
f[i][j] = min(f[i][j], f[i - k][j - k] + (sum[i] - sum[i - k]) * (i - k));
}
cout << f[n][m] << endl;
int i = n, j = m, t = 0;
while (i && j)
{
if (j >= i && f[i][j] == f[i][j - i]) j -= i, t ++ ;
else
{
for (int k = 1; k <= min(i, j); k ++ )
if (f[i][j] == f[i - k][j - k] + (sum[i] - sum[i - k]) * (i - k))
{
for (int u = i; u > i - k; u -- ) ans[g[u].y] = 1 + t;
i -= k, j -= k;
break;
}
}
}
for (int i = 1; i <= n; i ++ ) cout << ans[i] << " ";
cout << endl;
return 0;
}