题解：P14259 兄妹（siblings）

· · 题解

tag：背包。

暴力

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

特殊性质

设 r_i 的最大值为 m。

首先发现一行的书可以由同一个人解决，我们只需要对 m 行分别记录该行最大的 c，记这个值为 x_i。则当一个人负责一个下标集合 A 中的 x_i 时，最短总用时为 2\left(\max_{i\in A}i+\sum_{i\in A}x_i\right)，即来回最远的书架的用时加上对于每排负责的书架的来回用时。

那么问题可以转化为如下形式：将 x_i 分为两个组 Y,S，设每组下标最大值为 y,s（显然其一为 m，另一个小于 m），求 2\max\{y+\sum_{i\in Y}x_i,s+\sum_{i\in S}x_i\} 的最小可能值。

不妨设 y=m,s<m。则先贪心地找到使得 s+\sum_{i=1}^sx_i 与 y+\sum_{i=s+1}^mx_i 尽可能平均的最小 s，然后求出结果即可。注意判断 x_i 全为 2 的情况，可能无法完全均分。结合暴力期望得分 40。

背包

由如上讨论我们发现所有可能的方案总用时为对于某个 s，2\max\{y+\sum_{i\in Y}x_i,s+\sum_{i\in S}x_i\}，其中 y=m，S\subset \{1,\dots,s\}，Y\cup S=\{1,\dots,m\}。我们只要求出子集和就能计算出所有可能的答案，对其求最小值即可。

设计背包 dp，设 f_{i,j} 表示 \{1,\dots,i\} 的子集和是否可能为 j，则从 i-1 的可能值选择直接继承或加上 x_i 转移即可，即 f_{i-1,j}\to f_{i,j},f_{i,j+x_i}。转移总复杂度和统计答案的时间复杂度以及空间复杂度均为 O(m\sum x_i)，期望得分 90。

正解

发现测试点 10 的 r_i,c_i 可能达到 500，而空间限制只有 128\text{MB}，用滚动数组优化空间即可。事实上由转移方程的性质，从后往前枚举 j 转移只需开一维数组即可，空间复杂度变为 O(\sum x_i)，期望得分 100。

Code:

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";
}