【CH5105】cookies 贪心+DP

1. 通过邻项交换法可知，怨气值大的孩子分得的饼干数也应该多（否则交换之后得到的解更优）。
2. 观察目标函数的性质，可知目标函数本身是由孩子饼干数的相对大小得到，因此此题中关注的是相对大小。

状态设计：\(dp[i][j]\)表示前 i 个人分 j 个饼干的最小怨气值。(i，j)是问题的阶段

另外，在处理路径输出时，还是通过递归的操作，不过，这里是在递归时生成答案。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=31;

const int maxm=5001;

int dp[maxn][maxm],ans[maxn];

int n,m,num[maxn],sum[maxn];

struct node{

	int n,m;

}pre[maxn][maxm];

struct child{

	int g,idx;

}ch[maxn];

bool cmp(const child& x,const child& y){return x.g>y.g;}

void read_and_parse(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)scanf("%d",&ch[i].g),ch[i].idx=i;

	sort(ch+1,ch+n+1,cmp);//贪心

	memset(dp,0x3f,sizeof(dp));

	dp[0][0]=0;

}

void work(int i,int j){

	if(!i)return;

	work(pre[i][j].n,pre[i][j].m);

	if(pre[i][j].n==i)for(int k=1;k<=i;k++)ans[ch[k].idx]++;

	else for(int k=pre[i][j].n+1;k<=i;k++)ans[ch[k].idx]=1;

}

void solve(){

	for(int i=1;i<=n;i++){

		sum[i]=sum[i-1]+ch[i].g;//前缀和优化

		for(int j=i;j<=m;j++){

			dp[i][j]=dp[i][j-i];

			pre[i][j]=(node){i,j-i};

			for(int k=0;k<i;k++){

				if(dp[i][j]>dp[k][j-(i-k)]+k*(sum[i]-sum[k])){

					dp[i][j]=dp[k][j-(i-k)]+k*(sum[i]-sum[k]);

					pre[i][j]=(node){k,j-(i-k)};

				}

			}

		}

	}

	printf("%d\n",dp[n][m]);

	work(n,m);

	for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'\n':' ');

}

int main(){

	read_and_parse();

	solve();

	return 0;

}