链接:
https://www.acwing.com/problem/content/279/
题意:
圣诞老人共有M个饼干，准备全部分给N个孩子。
每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。
如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。
给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。
思路:
先考虑贪心,怨气较大的人得到的饼干肯定较多.
可以先进行排序, 再去进行DP, 考虑Dp使没有确定的值.
对于Dp[i,j]表示前i个孩子,共分配j个饼干的情况.
对于第i个孩子, 考虑将其分配大于1个饼干,可以发现将前i个人的饼干数都减一,并不影响答案的数值.
在考虑从i开始往前k个孩子全部分配1个饼干的情况,挨个查找.同时前缀和记录怨气的总值.
而为了找到每个孩子的具体数值.可以用a,b两个数组记录某个状态是由那个状态转移而来.
结束DP之后.递归查找.当某个状态是由孩子个数相同情况推出来的时候.可以将这些孩子的总数诶个加1.
否则可以得到k+1到n这些孩子的饼干数都为1.
其中还用到了神奇的排序...
代码:
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;int Dp[50][5010];
int G[50];
int Sum[50];
int C[50];
int a[50][5010], b[50][5010];
int Ans[50];
int n, m;bool cmp(int l, int r)
{return G[l] > G[r];
}void Ser(int n, int m)
{if (n == 0)return;Ser(a[n][m], b[n][m]);if (a[n][m] == n){for (int i = 1;i <= n;i++)Ans[C[i]]++;}else{for (int i = a[n][m]+1;i <= n;i++)Ans[C[i]] = 1;}
}int main()
{scanf("%d%d", &n, &m);for (int i = 1;i <= n;i++)scanf("%d", &G[i]), C[i] = i;for (int i = 0;i <= n;i++){for (int j = 0;j <= m;j++)Dp[i][j] = INF;}sort(C+1, C+1+n, cmp);Dp[0][0] = 0;for (int i = 1;i <= n;i++){Sum[i] = Sum[i-1]+G[C[i]];for (int j = i;j <= m;j++){Dp[i][j] = Dp[i][j-i];a[i][j] = i;b[i][j] = j-i;for (int k = 0;k < i;k++){if (Dp[i][j] > Dp[k][j-(i-k)]+k*(Sum[i]-Sum[k])){Dp[i][j] = Dp[k][j-(i-k)]+k*(Sum[i]-Sum[k]);a[i][j] = k;b[i][j] = j-(i-k);}}}}printf("%d\n", Dp[n][m]);Ser(n, m);for (int i = 1;i <= n;i++)printf("%d ", Ans[i]);printf("\n");return 0;
}