思路： dp[][]代表前i个小朋友发j个饼干的最小怒气值，由于排序不等式的证明，所有怒气值最高的小孩应该发的饼干是最大值，依次递减，我们先排序，然后记录在数组中原来的值，但是状态转移很难想啊，是类似整数划分，最后有几个饼干是等于1的，如果有k，K>0那么就可以由f[i][j]=min(f[i][j],f[i-k][j-k]+(i-k)*(sum[i]-sum[i-k]));，如果等于0的时候呢，由于这个怒气值取决于这个图形的形状，那么直接把整体往下-1就行了，最后比较ex的是要输出方案？？啊这，那就老老实实求吧，记录一个h，如果由第二个转移过来那就等价于把前i个小朋友发的饼干的抬高1。 ac代码：
#include<bits/stdc++.h> using namespace std; const int N=5010; int n; int m; int f[31][5010]; pair<int,int> g[31]; int sum[31]; int ans[N]; vector<int>res; int main() { cin >> n >> m; for(int i=1;i<=n;i++) { cin>>g[i].first; g[i].second=i; } sort(g+1,g+1+n); reverse(g+1,g+1+n); memset(f,0x3f,sizeof f); f[0][0]=0; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+g[i].first; for(int i=1;i<=n;i++) for(int j=i;j<=m;j++) { if(j==i) { f[i][j]=0; continue; } if(j>=i) f[i][j]=min(f[i][j-i],f[i][j]); for(int k=1;k<i;k++) f[i][j]=min(f[i][j],f[i-k][j-k]+(i-k)*(sum[i]-sum[i-k])); } int i=n; int j=m; int h=0; while(i) { if(f[i][j]==f[i][j-i]) { j-=i; h++; } else { for(int k=1;k<=i;k++) { if(f[i][j]==f[i-k][j-k]+(i-k)*(sum[i]-sum[i-k])) { for(int u=i-k+1;u<=i;u++) ans[g[u].second]=1+h; i-=k; j-=k; break; } } } } cout<<f[n][m]<<endl; for(int i=1;i<=n;i++) cout<<ans[i]<<' '; cout<<endl; return 0; }