专栏文章
P6418 题解
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mio72hzn
- 此快照首次捕获于
- 2025/12/02 14:25 3 个月前
- 此快照最后确认于
- 2025/12/02 14:25 3 个月前
天气要🔪人
感谢题解提供的思路
一.题目分析（极简看法）
个人
栋楼
次清楼操作
二.思路分析
1. 个人 栋楼
个人 , 我们要关注的是他们每个人是去哪栋楼至于他们的身份，来的时间先后并不重要所以我用个桶去记录每栋楼的人数就可以了每栋楼自然是 个人接着去按楼去处理就行（桶也有一点是因为 的范围小）
2. 次操作
看到这个，突然就想到这道题的 次操作可以被分解为 操作 和 次操作就是整个问题可以被分解几个子问题这不就是DP吗，仔细一看就是背包无疑
三.正解(详见code)
设 为前 栋楼用 次清楼操作后的最小噪音递推式 显然为答案当然就在 里了为 第 栋 , 用 次清楼操作后的最小噪音至于 的求法呢显然是将第 栋的人数分批均分清楼最好这样的清楼操作能将每次的噪音程度降低（最优了）而且这样分每块只有 或 的人分类讨论加和就可以了
四.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=x*10+c-'0';c=getchar();}
return x*f;
}
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/2*cnt1+(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;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...