【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;
}