//看题解写的 https://blog.csdn.net/sdfzyhx/article/details/51804748#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
int id,g;
bool operator<(
const node a)
const{
return g>
a.g;
}
}g[35];
int n,m,b[
35][
5050],pre[
35][
5050];
ll sum[35],dp[
35][
5050];
int main(){
freopen("cookies.in",
"r",stdin);
freopen("cookies.out",
"w",stdout);
scanf("%d%d",&n,&
m);
for(
int i=
1;i<=n;i++)scanf(
"%d",&g[i].g),g[i].id=
i;
sort(g+
1,g+
1+n);
//降序排列
for(
int i=
1;i<=n;i++)sum[i]=sum[i-
1]+
g[i].g;
memset(dp,0x3f,
sizeof dp);
dp[0][
0]=
0;
for(
int i=
1;i<=n;i++
)
for(
int j=i;j<=m;j++
){
dp[i][j]=dp[i][j-
i];
for(
int k=
1;k<=i;k++
){
if(dp[i][j]>dp[i-k][j-k]+(sum[i]-sum[i-k])*(i-k)){
//是保留原状态更优还是k-i区间都发一块饼干的状态更优
dp[i][j]=dp[i-k][j-k]+(sum[i]-sum[i-k])*(i-
k);
b[i][j]=
1;
//这个状态是发了一块饼干的
pre[i][j]=i-k;
//i-k+1 到 i都只发了一块饼干
}
}
}
printf("%lld\n",dp[n][m]);
int p=n,t=m,ans[
35]=
{};
while(p){
if(b[p][t]){
//只发了一块饼干的状态
int x=
pre[p][t];
for(
int i=x+
1;i<=p;i++
)
ans[g[i].id]++
;
t-=p-x;p=
x;
}
else {
//第一种状态转移，1-p所有阶梯都下降1
for(
int i=
1;i<=p;i++)ans[g[i].id]++
;
t-=
p;
}
}
for(
int i=
1;i<=n;i++) printf(
"%d ",ans[i]);
}
转载于:https://www.cnblogs.com/zsben991126/p/10216879.html
