FJ有M个牛棚，编号1至M，刚开始所有牛棚都是空的。FJ有N头牛，编号1至N，这N头牛按照编号从小到大依次排队走进牛棚，每一天只有一头奶牛走进牛棚。第i头奶牛选择走进第p[i]个牛棚。由于奶牛是群体动物，所以每当一头奶牛x进入牛棚y之后，牛棚y里的所有奶牛们都会喊一声“欢迎欢迎，热烈欢迎”，由于声音很大，所以产生噪音，产生噪音的大小等于该牛棚里所有奶牛（包括刚进去的奶牛x在内)的数量。FJ很讨厌噪音，所以FJ决定最多可以使用K次“清空”操作，每次“清空”操作就是选择一个牛棚，把该牛棚里所有奶牛都清理出去，那些奶牛永远消失。“清空”操作只能在噪音产生后执行。现在的问题是：FJ应该选择如何执行“清空”操作，才能使得所有奶牛进入牛棚后所产生的噪音总和最小？
第一行3个数n,m,k.
接下来n个数,第i个数表示第i头牛要进入哪一个牛棚.
输出一个最小噪音值.
样例:
7 1 4
1 1 1 1 1 1 1
输出:
9
n,m,k <= 500
分析：样例中给定的m=1的情况，分析一下可以发现我们要尽可能的把一个牛棚均匀分成k段，那么我们只需要在k+1等分点上清空就好了.通过暴力可以得到40分.
考虑贪心，我们将清空次数尽量分给牛多的牛棚，可以骗到80分.
正解是dp.m=1的情况可以告诉我们第i个牛棚清空j次都是有最优解的，那么我们可以求出f[i][j],表示第i个牛棚清空j次的最小噪音值。这样我们可以枚举第几个牛棚清空几次.然后可以发现这就是背包问题,再开一个数组f2[i][j]表示1~i个牛棚中清空j次的最小噪音值，就可以解决了.
求出f数组是一个难点.假设我们要把第i个牛棚清空j次，那么实际上我们就是把第i个牛棚分成了j+1段，我们的目的是把每一段的牛的数量尽可能的靠近num[i] / (j + 1),但是有可能不能平均分，这个时候就有一些段要分num[i] / (j + 1) + 1头牛，具体有多少段呢？num[i] % (j + 1),平均分的段数自然也就出来了.
这道题的关键就是各个牛棚之间不互相影响，那么对于每一个局部部分我们可以先算出局部最优解，最后合并成全局最优解，是一种通用的技巧.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int maxn = 510; long long n,m,k,num[maxn],f[maxn][maxn],f2[maxn][maxn]; long long cal(long long x) { return x*(x + 1) / 2; } int main() { scanf("%lld%lld%lld",&n,&m,&k); for (long long i = 1; i <= n; i++) { long long t; scanf("%lld",&t); num[t]++; } for (int i = 1; i <= m; i++) { f[i][0] = cal(num[i]); for (int j = 1; j <= k; j++) { int t1 = num[i] % (j + 1); int t2 = j + 1 - t1; f[i][j] = t2 * cal(num[i] / (j + 1)) + t1 * cal(num[i] / (j + 1) + 1); } } for (int i = 1; i <= m; i++) for (int j = 0; j <= k; j++) { f2[i][j] = f2[i-1][j] + f[i][0]; for (int l = 1; l <= j; l++) f2[i][j] = min(f2[i][j],f2[i-1][j-l] + f[i][l]); } printf("%lld ",f2[m][k]); return 0; }