题目传送门：P6418 [COCI 2014/2015 #1] ZABAVA

解题思路

问题分解：

1. 每栋楼的吵闹指数是独立的，可以分别计算每栋楼的最小吵闹指数，然后求和。

2. 对于每栋楼，我们需要决定在哪些时刻进行清空操作，以最小化该楼的吵闹指数之和。

算法：动态规划

• 对于每栋楼，我们可以使用动态规划来计算在 $k$ 次操作内，如何安排清空操作以最小化吵闹指数。

• 定义 $dp[i][j]$ 表示在第 $i$ 个学生搬进该楼时，已经进行了 $j$ 次清空操作的最小吵闹指数之和。

转移方程：

• 如果不进行清空操作，$dp[i][j] = dp[i-1][j] + dp_{currentstudent}$。

• 如果进行清空操作，$dp[i][j]=dp[i-1][j-1]+1$（因为清空后当前学生是第一个，吵闹指数为 1）。

最终结果为 $dp[n][k]$。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,i,j,x,k1,k2,num,sum,m2,a[501],dp[501][501];
int cmp(int i,int j,int k1)
{
    k2=j-k1;
    m2=a[i]/(k2+1);
    sum=(m2+1)*(k2+1)-a[i];
    num=(k2+1)-sum;
    sum=sum*m2*(m2+1)/2+num*(m2+1)*(m2+2)/2;
    return sum;
}
signed main()
{
    cin>>n>>m>>k;
    for(i=1;i<=n;i++){
        cin>>x;
        a[x]++;
    }
    for(i=1;i<=m;i++){
    	for(j=0;j<=k;j++){
    		dp[i][j]=0x3f3f3f3f;
		}
	}           
    for(i=1;i<=m;i++){
    	for(j=0;j<=k;j++){
    		for(k1=0;k1<=j;k1++){
    			dp[i][j]=min(dp[i][j],dp[i-1][k1]+cmp(i,j,k1));
			}
		}
	}
    cout<<dp[m][k]<<endl;        
                    
    return 0;
}