专栏文章

题解：P6418 [COCI 2014/2015 #1] ZABAVA

xxumaokang
P6418题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio73rhg
此快照首次捕获于
2025/12/02 14:26
3 个月前
此快照最后确认于
2025/12/02 14:26
3 个月前
查看原文

分析

每次加入学生的代价为该公寓的学生数，能清空一次公寓 最多k次 用 dpidp_i ,_, j_j 表示前i栋用了j次操作清空公寓 状态转移是 dpdp i_i ,_, j_j =min(=min( dpidp_i ,_, j_j , dpidp_i −_- 1_1 ,_, k_k k_k +solve(i,j−kk));+solve ( i , j-kk )); dpdp很好想，但是 solvesolve里是什么呢？

slove函数

首先，对于 n=5,m=1,k=2n=5,m=1,k=2 来说，把清空操作当做隔板，mm的个数是隔板的数量，因此，我们可以得到 m+1m+1个区间
于是我们可以把 nn分成 m+1m+1个，每个是 n/(m+1)n/(m+1) ，o/o/oooo/o/o o o ，答案就是 1+1+（1+2+3）=81+1+（1+2+3）=8 但这样分不够平均，可以把第二个挡板向右平移一格，o/oo/ooo/oo/oo ，这样答案是 1+(1+2)+(1+2)=71+(1+2)+(1+2)=7 但我们什么时候能知道分的平均呢，如果上取整，对于 n=5，m=1，k=2n=5，m=1，k=2是平均的，但对于 n=7，m=1，k=2n=7，m=1，k=2 ，不上取整才平均，难道我们要取max吗？
其实不然，当 m=1m=1 时，我们可以类比一下小学二年级学的鸡兔同笼，鸡有 n/(m+1)n/(m+1)条腿，兔有 n/(m+1)+1n/(m+1)+1 条腿，（因为每个相邻隔板之间的 距离差 最多差一）现有 nn条腿，求有多少只鸡和兔，具体细节见代码注释
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n ,m ,k ;
int b[105] ,dp[105][505] ;
int solve (int i , int kk)
{
	int minn = b[i] / (kk + 1);//鸡爪的大小
	int sum = (minn + 1) * (kk + 1) - b[i];//minn+1是兔腿的大小，（minn+1）*（kk+1）是假设区间内全是兔子，有多少个腿，-b[i],是多出来的腿数，根据二年级数学，多出来的腿数/腿的差就是鸡的数量，因为差为1，所以sum/1就是鸡的数量，即sum
	int num = kk + 1 - sum;//总个数减鸡的个数是兔的个数
	return sum * minn * (minn + 1) / 2+ num * (minn + 1) * (minn + 2) / 2; //鸡的个数*（鸡区间的价值）+兔的个数*（兔区间的价值）
}
signed main()
{
	cin >> n >> m >> k;
	for (int i = 1 , x ; i <= n ; i++) {
		scanf("%lld", & x);
		b[x]++;
	}
	for (int i = 1 ; i <= m ; i++)
		for (int j = 0 ; j <= k ; j++)
			dp[i][j]=1e18;
	for (int i = 1 ; i <= m ; i++)
		for(int j = 0 ; j <= k ; j++)//背包，先算出来dpij，后面接着用
			for(int kk = 0 ; kk <= j ; kk++)//i栋楼用了j-kk次操作
				dp[i][j] = min ( dp[i][j] , dp[i-1][kk] + solve ( i , j-kk ));
	cout << dp[m][k] << endl;
	return 0;
}
dpdp的具体细节dalao们的代码中已经很详细了，这里不具体展开了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...