前置芝士
动态规划 / DP
子集划分问题 / 可行性背包
思路
首先观察这个放书的性质。结论：对于在同一个书架上的书，只需要一个人去负责。
证明也比较简单，考虑某个人去放了这一排最远的（
最大的）书，那么它一定可以顺带放路上经过的所有的书。有了这个结论，就可以推出：在第
个书架放书的用时是固定的，就是：
。
那么这个问题转化成了：
有
（
为最大书架编号）个数字，把他划分成两组，求两组内部元素的和的最大值的最小值。
但是由于从一个书架移动到另一个还要花费时间，所以还有额外的代价。考虑去放书的时候移动一定是按照下标递增顺序的，同理，放完书回来也不用回头，所以下标一定单调递减。设第一组的总和为
，最大下标为
，第二组的总和为
，最大下标最大为
；则代价为
。你需要求这个代价的最小值。
上述第一个问题，是一个经典的“子集划分”问题。直接跑可行性背包加上 std::bitset 优化即可。
对于第二个问题，比较复杂，我们继续观察性质：注意到，由于这两组的并集是全集，所以
和
一定有一个是
。
这样，我们可以固定
，然后枚举，从
至
枚举
的值。接下来考虑如何做到
。由于
表示最大下标，所以任意
的下标都不能划分至第一组。
还是可行性背包，但是有了初始代价。
第一组初始代价是在书架之间走路所花费的
；
令
，
，则第二组的初始代价是在书架之间走路的代价
加上下标
的所有书架放书的代价：
；第二组的总初始代价为
。
这个时候再去跑可行性背包，使得两部分尽量平均即可。
Code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
inline int read(){/*快读模板 略*/};
int cost[505];
bitset<250005> used;
void solve(){
for(int i=1;i<=500;i++) cost[i]=0;
int n=read(),m=0;
for(int i=1;i<=n;i++){
int r=read(),c=read();
cost[r]=max(cost[r],c);
m=max(m,r);
}
used.reset();
used.set(0);
int cnt=0,sum=0,ans=3e15;
for(int i=1;i<=m;i++) cost[i]*=2,sum+=cost[i];
for(int i=1;i<m;i++){
cnt+=cost[i];
used|=(used<<cost[i]);//可行性背包
int a=m*2+sum-cnt,b=i*2;//a是第二组的初始代价，b是第一组的初始代价
if(cnt<a-b){
ans=min(ans,a);//无法达到两个相等，直接取较大值
}else{
ans=min((int)(b+(cnt+a-b+1)/2+(used>>((cnt+a-b+1)/2))._Find_first()),ans);//可行性背包：寻找最接近平均值的数
ans=min((int)(a+(cnt-a+b+1)/2+(used>>((cnt-a+b+1)/2))._Find_first()),ans);
}
}
cout<<ans<<endl;
}
main(){
int T=read();
while(T--) solve();
return 0;
}
