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