题目描述
ZCC终于打开了密码箱，发现里面只是一堆风干的肉条，于是他打算喂狗。
ZCC养了n条狗，有m根肉条，他想把肉条一根不留地分给狗，并使得每条狗至少有一条肉条可吃。狗总是很贪心，它们不希望看到有其他的狗有更多的肉条，否则就会不开心。一条狗的不开心程度可以表示为他的贪心程度和拥有比它更多肉条的狗的数量的乘积。现在ZCC想知道一种分配方式使得狗们的不开心程度的和最小。
题解
这题非常玄妙，看到这道题有没有想到整数划分？没有想到就可以自闭了（想到了也自闭了）。然后我们可以用类似的方法DP。显然我们先排序，这里降序排。
记f[i][j]f[i][j]f[i][j]表示做到第iii个，用了jjj块肉的状态。假如第iii块用了大于1块的肉则这个状态和f[i][j−i]f[i][j-i]f[i][j−i]是一样的，全部取掉1。假如不是1，那么枚举和它相连的有几个1
f[i][j]=min(f[i][j−i],f[k][j−(i−k)]+k∗(sum[i]−sum[k]))f[i][j]=min(f[i][j-i],f[k][j-(i-k)]+k*(sum[i]-sum[k]))f[i][j]=min(f[i][j−i],f[k][j−(i−k)]+k∗(sum[i]−sum[k]))
我们还要求方案，显然记录下来方案的路径
如果两个方案的iii相同说明是从所有减1转移来的，要全部加1
反正说明是从前面一些位置全是1转移过来的，那些位置加1即可
代码
#include <bits/stdc++.h>#define maxn 55#define MAXN 5005#define INF 0x3f3f3f3f#define LL long long#define P pair<int,int>#define MP make_pairusing namespace std;int read(){int res,f=1; char c;while(!isdigit(c=getchar())) if(c=='-') f=-1; res=(c^48);while(isdigit(c=getchar())) res=(res<<3)+(res<<1)+(c^48);return res*f;}int n,m,ans[maxn],D[maxn],d[maxn],g[maxn],f[maxn][MAXN],sum[maxn];bool cmp(int x,int y){return g[x]>g[y];}P path[maxn][MAXN];int main(){memset(f,0x3f,sizeof f);n=read(); m=read();for(int i=1;i<=n;i++) d[i]=i,g[i]=read();stable_sort(d+1,d+n+1,cmp);for(int i=1;i<=n;i++) sum[i]=g[d[i]]+sum[i-1];f[0][0]=0;for(int i=1;i<=n;i++){for(int j=i;j<=m;j++){f[i][j]=f[i][j-i];path[i][j]=MP(i,j-i);for(int k=0;k<i;k++){if(f[i][j]>f[k][j-(i-k)]+k*(sum[i]-sum[k])){f[i][j]=f[k][j-(i-k)]+k*(sum[i]-sum[k]);path[i][j]=MP(k,j-(i-k));}}}}printf("%d\n",f[n][m]);P x=MP(n,m);while(x.first && x.second){P y=path[x.first][x.second];if(x.first==y.first) for(int i=1;i<=x.first;i++) ans[d[i]]++;else for(int i=y.first+1;i<=x.first;i++) ans[d[i]]++;x=y;}for(int i=1;i<=n;i++) printf("%d ",ans[i]);return 0;}
