题目描述：
圣诞老人共有MM个饼干，准备全部分给N个孩子。
每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。
如果有 a[i]a[i] 个孩子拿到的饼干数比第 ii 个孩子多，那么第 ii 个孩子会产生 g[i]×a[i]的怨气。
给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。
输入格式 第一行包含两个整数N,M。
第二行包含N个整数表示g1~gN。
输出格式 第一行一个整数表示最小怨气总和。
第二行N个空格隔开的整数表示每个孩子分到的饼干数，若有多种方案，输出任意一种均可。
数据范围 1≤N≤30,N≤M≤5000,1≤gi≤10^7 输入样例： 3 20 1 2 3 输出样例： 2 2 9 9
解题思路：
根据序列不等式，或者感性理解，容易得知贪心策略是要让贪婪度大的孩子得多一点糖糖（所谓会哭的孩纸有糖吃），这样我们就把答案可能存在的集合大大缩小我们根据贪婪度从大到小排序，对于糖果的分配就是非严格递减观察这道题，我们发现一个大大的突破口：这道题只在意孩子之间的相对高度，而不在意绝对高度，举个例子：2 4 4 6 产生的结果和 1 2 2 3 是一样的（所谓幸福感是比较出来的）这个发现有什么好处呢？那就是大大减少了枚举！一些相对高度相同的状态（称为相似状态）我们不需要细致探究，而可以直接继承之前出现过的相似状态。假设我们已经处理到了第 i 个孩子，我们给她分配糖糖的时候就很轻松。要么让她得到大于1个糖果，那么这个状态什么也不用考虑，可以直接继承上一个状态。例如：前面的糖果分配方案是： 100 30 5 X（X是当前的孩纸）我想给当前的孩纸分配3个糖果，那么这个状态的效果即为（100，30，5，3）=（99，29，4，2）=（98，28，3，1）要么让她得到1个糖果，那么这个状态就要考虑（因为它没得直接继承）——前面有多少个孩纸跟她得到同样多的糖果（也就是1个糖果），因为并列的孩纸是不累积到怨气值的（例如 2 2 2 2 2 2，所有孩子都有一样的糖果数，所以是没有怨气值的），假设前面有K个孩子跟她糖果数相同（K包括她自己），那么就有（i-k）个孩子比她们多得糖果，那么怨气值就是前（i-k）个孩子（管他怎么分配的）最小怨气值+（i-k）挨个乘上这K个孩子的贪婪度你可能会说最后一个孩子不一定要1个糖果啊，但是只要她不要一个糖果，她就可以继承前面只要一个糖果的状态状态设置：f[i][j]表示当前处理到第I个孩子，分配了j个糖果状态转移：f[i][j]= min ( f[i][j-i] ，f[i-k][j-k]+(i-k)*每个的贪婪度）【其中K需要枚举】 至于最后的方案，我们可以用一个数组保存，然后回溯输出。完整代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { char c=getchar();int f=1,s=0; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){s=s*10+c-'0';c=getchar();} return f*s; } int f[31][5010]; int n,m; struct child { int d,ip; }g[31]; inline bool cmp(child n1,child n2){return n1.d>n2.d;} inline int mymin(int x,int y){return x<y?x:y;} int cumu[31]; struct state { int nd,t; }a[31][5010]; int ans[31]; int main() { n=read();m=read(); for(int i=1;i<=n;i++) g[i].d=read(),g[i].ip=i; sort(g+1,g+n+1,cmp); memset(f,63,sizeof(f)); for(int i=1;i<=n;i++)cumu[i]=cumu[i-1]+g[i].d,f[i][0]=0,a[i][0].nd=0,a[i][0].t=i; for(int i=1;i<=n;i++) { for(int j=i;j<=m;j++) { if(f[i][j-i]<f[i][j]) { f[i][j]=f[i][j-i]; a[i][j].nd=a[i][j-i].nd+1; a[i][j].t=a[i][j-i].t; } for(int k=1;k<=i;k++) { if(f[i-k][j-k]+(i-k)*(cumu[i]-cumu[i-k])<f[i][j]) { f[i][j]=f[i-k][j-k]+(i-k)*(cumu[i]-cumu[i-k]); a[i][j].nd=1;a[i][j].t=k; } } } } printf("%d\n",f[n][m]); int now=n,sum=m; while(now) { int dd=a[now][sum].nd; int tt=a[now][sum].t; ans[g[now].ip]=dd; for(int i=now;i>=now-tt+1;i--) { ans[g[i].ip]=dd; } now-=tt; sum-=dd*tt; } for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }
