題目描述：
圣誕老人共有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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162784.html
標籤：java
上一篇：一道題解釋樹形dp【此后無良辰】