【階段1】【貪心】【動態規劃】餅乾

題目描述：

聖誕老人共有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;
}