bzoj1082: [SCOI2005]栅栏http://www.lydsy.com/JudgeOnline/problem.php?id=1082
巨有意思（神tm）的一道题
看了题解还写了很多注释理解 hmmm……
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[60],b[1100],sa,sb[1100]; int v[1100]; int m,n,l,r,mid,ans,wa;//wa:waste如果这块木板割过之后比第一块木板的还小的话就算做浪费的 bool cmp(int x,int y) { return x<y; } bool dfs(int x,int last) { bool bk; if (x==0) return 1; if (sb[x]+wa>sa) return 0;//现在已经能割出来木板长度加上浪费的已经比能提供的木板总长大 木板已用完 直接退出 for (int i=last;i<=m;i++) { if (b[x]<=a[i]) { a[i]-=b[x]; if (a[i]<b[1]) wa+=a[i]; if (b[x-1]==b[x]) bk=dfs(x-1,i); //相等的话以为这一次已经搜过了直接往大的木板搜就可以了 else bk=dfs(x-1,1);//因为是从大的往小的搜 所以前面用过的说不定也可以满足 if (a[i]<b[1]) wa-=a[i]; a[i]+=b[x]; if (bk) return bk; } } return 0; } int main() { scanf("%d",&m); for (int i=1;i<=m;i++) {scanf("%d",&a[i]);sa+=a[i];} scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&b[i]); sort(a+1,a+1+m,cmp); sort(b+1,b+1+n,cmp); //排序剪枝：如果大的满足了那么小的就很好满足了 for (int i=1;i<=n;i++) sb[i]=sb[i-1]+b[i]; l=0;r=n; //能满足的木板肯定是最小的那几块啊 //二分的东东=能满足多少块木板=最大的木板编号=从哪一块开始往前dfs（从大到小往前dfs） while (l<=r) { mid=(l+r)/2; if (dfs(mid,1)) { ans=mid; l=mid+1; } else r=mid-1; } printf("%d\n",ans); return 0; }