专栏文章

题解：P14259 兄妹（siblings）

VVinstaG173かえで
P14259题解参与者 19已保存评论 18

文章操作

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

当前评论
18 条
当前快照
1 份
快照标识符
@minrshox
此快照首次捕获于
2025/12/02 07:18
3 个月前
此快照最后确认于
2025/12/02 07:18
3 个月前
查看原文
tag：背包。

暴力

直接分配每本书共 O(2n)O(2^n) 种可能，O(n)O(n) 统计用时，期望得分 1010。

特殊性质

设 rir_i 的最大值为 mm。
首先发现一行的书可以由同一个人解决，我们只需要对 mm 行分别记录该行最大的 cc，记这个值为 xix_i。则当一个人负责一个下标集合 AA 中的 xix_i 时，最短总用时为 2(max⁡i∈Ai+∑i∈Axi)2\left(\max_{i\in A}i+\sum_{i\in A}x_i\right)，即来回最远的书架的用时加上对于每排负责的书架的来回用时。
那么问题可以转化为如下形式：将 xix_i 分为两个组 Y,SY,S，设每组下标最大值为 y,sy,s（显然其一为 mm，另一个小于 mm），求 2max⁡{y+∑i∈Yxi,s+∑i∈Sxi}2\max\{y+\sum_{i\in Y}x_i,s+\sum_{i\in S}x_i\} 的最小可能值。
不妨设 y=m,s<my=m,s<m。则先贪心地找到使得 s+∑i=1sxis+\sum_{i=1}^sx_i 与 y+∑i=s+1mxiy+\sum_{i=s+1}^mx_i 尽可能平均的最小 ss，然后求出结果即可。注意判断 xix_i 全为 22 的情况，可能无法完全均分。结合暴力期望得分 4040。

背包

由如上讨论我们发现所有可能的方案总用时为对于某个 ss，2max⁡{y+∑i∈Yxi,s+∑i∈Sxi}2\max\{y+\sum_{i\in Y}x_i,s+\sum_{i\in S}x_i\}，其中 y=my=m，S⊂{1,…,s}S\subset \{1,\dots,s\}，Y∪S={1,…,m}Y\cup S=\{1,\dots,m\}。我们只要求出子集和就能计算出所有可能的答案，对其求最小值即可。
设计背包 dp，设 fi,jf_{i,j} 表示 {1,…,i}\{1,\dots,i\} 的子集和是否可能为 jj，则从 i−1i-1 的可能值选择直接继承或加上 xix_i 转移即可，即 fi−1,j→fi,j,fi,j+xif_{i-1,j}\to f_{i,j},f_{i,j+x_i}。转移总复杂度和统计答案的时间复杂度以及空间复杂度均为 O(m∑xi)O(m\sum x_i)，期望得分 9090。

正解

发现测试点 1010 的 ri,cir_i,c_i 可能达到 500500，而空间限制只有 128MB128\text{MB}，用滚动数组优化空间即可。事实上由转移方程的性质，从后往前枚举 jj 转移只需开一维数组即可，空间复杂度变为 O(∑xi)O(\sum x_i)，期望得分 100100。
Code:
CPP
int n,r,c;
int x[503];
int f[250003],ans;
inline void solve(){
	for(int i=1;i<=500;++i)x[i]=0;
	for(int i=1;i<=250000;++i)f[i]=0;
	cin>>n;while(n--){
		cin>>r>>c;
		x[r]=max(x[r],c);
	}for(r=500;!x[r];--r);
	c=0;f[0]=1;ans=3e5;
	for(int i=1;i<=r;++i)c+=x[i];
	for(int i=1,s=0;i<=r;++i){
		if(!x[i])continue;
		for(int j=s;j>=0;--j)
			if(f[j])f[j+x[i]]=1;
		s+=x[i];
		for(int j=0;j<=s;++j)
			if(f[j])
				ans=min(ans,max(i+j,r+c-j));
	}cout<<ans*2<<"\n";
}

评论

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

正在加载评论...