P6418 题解

· · 个人记录

天气要🔪人

感谢题解提供的思路

一.题目分析（极简看法）

$m$ 栋楼 \ $k$ 次清楼操作

二.思路分析

1. n个人 m栋楼

**他们每个人是去哪栋楼** 至于他们的身份，来的时间先后并不重要 **所以我用个桶去记录每栋楼的人数就可以了** 每栋楼自然是 $t[i]$ 个人 接着去按楼去处理就行（桶也有一点是因为 $m$ 的范围小）

2. k次操作

看到这个，突然就想到这道题的 k 次操作

可以被分解为 j 操作 和 k-j 次操作

就是整个问题可以被分解几个子问题

这不就是DP吗，仔细一看就是背包无疑

三.正解(详见code)

设 dp[i][j] 为前 i 栋楼用 j 次清楼操作后的最小噪音

递推式 显然为

dp[i][j]=min ({dp[i-1][k]+solve(i,j-k)})

答案当然就在 dp[m][k] 里了

至于 $solve(i,j)$ 的求法呢 显然是将第 $i$ 栋的人数分批均分清楼最好 这样的清楼操作能将每次的噪音程度降低（最优了） 而且这样分每块只有 $(\displaystyle \frac{t[i]}{k+1})$ 或 $(\displaystyle \frac{t[i]}{k+1} + 1)$ 的人 分类讨论加和就可以了 ## 四.code代码 ```cpp #include<bits/stdc++.h> #define ll long long #define N 555

using namespace std; ll read(){//快读 ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x10+c-'0';c=getchar();} return xf; } ll n,m,k,x; ll t[N],dp[N][N];//桶 and DP数组 ll solve(ll i,ll k){ k++; //k 次清楼操作，将人分成 (k+1) 块 ll siz=t[i]/k; //t[i] 个人，每块至少 siz 个人 ll cnt1=(1+siz)k-t[i]; // 求（siz+1）人的块数 ll cnt2=k-cnt1; // 求（siz） 人的块数 ll sum=(1+siz)siz/2cnt1+(1+siz+1)(siz+1)/2*cnt2;

return sum; }

int main(){ n=read(),m=read(),k=read(); for(int i=1;i<=n;i++)t[x=read()]++; memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; // 边界 //普通的背包 for(int i=1;i<=m;i++)//枚举楼 i for(int j=0;j<=k;j++)// 枚举清楼次数 j for(int l=0;l<=j;l++)//枚举前 (i-1) 栋的清楼次数 l dp[i][j]=min(dp[i][j],dp[i-1][l]+solve(i,j-l)); // 递推公式 !!! cout<<dp[m][k]<<"\n";
return 0; }