有m块饼干，全部分给n个孩子，第i个孩子有个贪婪度(g_i),如果有(a_i)个孩子比第i个孩子的饼干多，则增加(a_i imes g_i)的怒气值，要求每个孩子至少分到一块饼干，现在寻找一种方案使总怒气值最低，(1≤N≤30, N≤M≤5000)。
解
首先贪心可知道，在一种最优的方案中，如果存在一对孩子，一个贪婪度低，分的饼干多，一个贪婪度高，分的饼干少，于是交换这两者分的饼干，必然结果会更加优秀，于是最优方案随贪婪度的递增，分的饼干递增。
让孩子按照贪婪度从小到大排序,于是我们得设我们现在处理到哪一个孩子，还有总共已经分了多少块饼干，为了保证递减性，我们还得维护这个孩子分了几块饼干，显然会超时，于是显然不能表现该孩子分了几块饼干。
但注意到一个孩子可以分多块饼干，类似完全背包，而我们只在乎相对大小关系，可以考虑阶段内转移优化，而孩子分的饼干的一种方案，饼干数都会有共同的相等的部分，也就是减去不改变怒气值，只改变了总饼干数。
于是可以这样考虑，忽略上面所说的第三维，现在把g数组变为前缀和，设(f[i][j])表示处理到第i个孩子，已经分走了j块饼干的最小怒气值，如果当前孩子只分一块饼干，我只要枚举前面有多少人分的饼干数与之相同，否则只要把每个人的饼干数减掉i不影响怒气值，于是有
[f[i][j]=max(f[i][j-i],max_{k=0}^{i-1}(f[k][j-(i-k)]+g[i]-g[k]))
]
边界：(f[0][0]=0)，其余无限大
答案：(f[n][m])
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <functional>
#include <algorithm>
#define il inline
#define ri register
#define ll long long
using namespace std;
struct DATA{
ll g;int id;
}d[31];
ll g[31],dp[31][5001];
int ans[31],pre[31][5001];
il bool comp(const DATA &a,const DATA &b){
return a.g>b.g;
}
int main(){
int n,m,i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
scanf("%lld",&d[i].g),d[i].id=i;
sort(d+1,d+n+1,comp);
for(i=1;i<=n;++i)g[i]=d[i].g+g[i-1];
memset(dp,1,sizeof(dp)),dp[0][0]=0;
for(i=1;i<=n;++i)
for(j=i;j<=m;++j){
dp[i][j]=dp[i][j-i],pre[i][j]=i;
for(k=0;k<i;++k)
if(dp[i][j]>dp[k][j-(i-k)]+(g[i]-g[k])*k)
dp[i][j]=dp[k][j-(i-k)]+(g[i]-g[k])*k,
pre[i][j]=k;
}
printf("%lld
",dp[n][m]);
i=n,j=m;
do{
if(pre[i][j]==i){
for(k=1;k<=i;++k)++ans[d[k].id];
j-=i;
}
else{
for(k=pre[i][j]+1;k<=i;++k)
++ans[d[k].id];k=pre[i][j];
j-=(i-k),i=k;
}
}while(i);
for(i=1;i<=n;++i)printf("%d ",ans[i]);
return 0;
}