题解——P2329 [SCOI2005]栅栏
解题分析
看到这个题面，自然会想到一个二分模板题，其思路是对于答案进行二分，回过头判断当前的答案是否可以被满足。那么本题和上一题的区别在于，需求的木板长度也是不一样的，对应的解决措施是把循环实现的判断函数改为搜索。
实现
基本操作
首先进行升序排序以保证木材被最大化的利用，然后进行二分。二分的区间为 \([0,n]\) 意义是能否满足前 \(mid\) 个木块的需要，区间的缩减是：
if(check()) ans=mid,l=mid+1;
else r=mid-1;
这里用 \(ans\) 记录答案，不需要缩小边界时不需要包括 \(mid\)。同时注意每次搜索判断时都要把木材数组初始化，建议开一个 \(tmp\) 数组。
优化
这样的搜索显然是会 \(TLE\) 的，考虑两方面的优化。
关于二分区间
可以发现，如果木材总长度小于需求木板总长度，一定是无法实现的，并且会占用时间，所以可以通过该判断缩小右边界 \(n\)。
while(suma关于搜索剪枝
先来看初始版本的搜索：
inline bool check(int pos){
if(!pos) return 1;
for(int i=1;i<=m;i++){
if(tmp[i]>=q[pos]){
tmp[i]-=q[pos];
if(check(pos-1) return 1;
tmp[i]+=q[pos];
}
}
return 0;
}
大致思路是：倒序搜索木材正序枚举木料，如果能够满足全部就返回值为真。
先考虑可行性剪枝，和对二分区间的优化相同，如果目前的剩余木材小于木板总长度，那么一定不可行。需要更新变量 \(waste\)，注意回溯顺序。
其次是比较玄学的剪枝，如果下一块木板和这一块木板长度相同，那么下次枚举从当前木材开始即可，原因是前面的木材都无法满足当前木板长度。
代码
int n,m;
int a[1005],q[1005],tmp[1005];
int suma,sumq[1005];
int l,r,mid;
inline bool check(int pos,int last,int waste=0){
if(waste>suma-sumq[mid]) return 0;
if(!pos) return 1;
for(int i=last;i<=m;i++){
if(tmp[i]>=q[pos]){
tmp[i]-=q[pos];
if(tmp[i]>1;
for(int i=1;i<=n;i++){
tmp[i]=a[i];
}
if(check(mid,1)){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
printf("%d\n",ans);
return 0;
}