饼干 （贪心+dp+奇妙转换）

思路：
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;
}