5105 Cookies 0x50「动态规划」例题
描述
圣诞老人共有M个饼干，准备全部分给N个孩子。每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。1≤N≤30, N≤M≤5000, 1<=gi<=10^7。
输入格式
第一行两个整数N,M，第二行N个整数g1~gN。
输出格式
第一行一个整数表示答案，第二行N个整数表示每个孩子分到的饼干数。本题有SPJ，若有多种方案，输出任意一种均可。
样例输入
样例输入1 3 20 1 2 3 样例输入2 4 9 2 1 5 8
样例输出
样例输出1 2 2 9 9 样例输出2 7 2 1 3 3
来源
ITMO
思路，很容易想明白的一点是:每一个小孩拿到的饼干和他的愤怒值成正相关，(如果非正相关可以通过交换两个人的饼干数来达到优化)。然后进行状态判断，此题状态表示很好想，一开始我想用三维数组来表示，f[i][k][s]分别表示当前第几个小孩，拿到几个饼干，还剩几个饼干，显然三维数组内存超限，这就促使我们将三维变成二维数组,f[i][j]表示当前第i个小孩拿到总共j块饼干的最小值,另外注意到一点就是无法确定之前i-1个小孩分别拿了几块饼干;这就使得我们需要进行状态转换,我们将集合划分成第i个小孩拿到是否为1块饼干,进行分类讨论;
第i个小孩拿到1块饼干,那么这时就将问题转化为前面有多少人和他一样？这样做的好处是正好我们会知道前面k个人拿到了总共k块饼干,从而确定状态是f[i-k][j-k]+(sum[i]-sum[i-k])*(i-k);
第i个小孩拿到多于1块饼干,第i个小孩的饼干数都多于1了,我们序列是单调递减的,一个基本要求就是所拿到的饼干数是递减的,所以可以将他转换成第i个小孩拿到1块饼干的状态,即这个状态的值和f[i][j-i]取min;注意这里是指的是f[i][j]与f[i][j-i]在取值上是相同的,然后对于每一项,f[i][j]均比f[i][j-1]多了个1;
关于每一个小孩状态的转换来看,我们可以从后向前来递推的得到具体方案,对于每一项进行判断他是否由f[i][j-i]递推过来,若是,那么整个都＋1;否则进行判断他与那个f[i-k][j-k]相同;
code:
/*************************************************************************
> File Name: Acwing.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
> Created Time: 2020年12月11日 星期五 10时27分11秒
************************************************************************/
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 5e3+10,inf = 0x3f3f3f3f;
int n,m,f[38][N],now[39][N];
bool cmp(int a,int b){
return a>b;
}
pair<int,int>g[49];
int sum[49],ans[40];
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&g[i].first),g[i].second = i;
sort(g+1,g+1+n);
reverse(g+1,g+1+n);
rep(i,1,n)sum[i] = sum[i-1] + g[i].first;
memset(f,inf,sizeof f);
f[0][0] = 0;
rep(i,1,n){
rep(j,1,m){
if(j>=i)f[i][j] = min(f[i][j],f[i][j-i]);
rep(k,1,min(i,j)){
f[i][j] = min(f[i-k][j-k]+(i-k)*(sum[i]-sum[i-k]),f[i][j]);
}
}
}
printf("%d\n",f[n][m]);
//求具体方案;
int i=n,j=m,h=0;
while(i&&j){
if(j>=i&&f[i][j] == f[i][j-i])j-=i,h++;
else {
rep(k,1,min(i,j)){
if(f[i][j] == f[i-k][j-k]+(sum[i]-sum[i-k])*(i-k)){
for(int u=i;u>i-k;--u)ans[g[u].second] = 1+h;
i-=k;j-=k;
break;
}
}
}
}
rep(s,1,n)printf("%d ",ans[s]);
puts("");
}
int main(){
solve();
return 0;
}
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
