题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1082
二分+dfs判定。
显然我们取的肯定是前ans块木板。然后砍的木材也应该是从小到大砍（如果小的木材可以满足条件我一定不会去动大的木材嘛。
所以两遍排序。二分答案。
然后对于要取的每块木板，我们搜索它是在第x块木板上砍下来的。。
要加剪枝：①如果砍下了这块木材然后这块木材小于第一块木板，那就失去价值，开个rest来记录。当rest+sum[dep]>s那么退出。
②如果b[dep]==b[dep-1]那么从当前点开始枚举就可以了，因为前面小的点都被我跳掉了。。
感觉还是很有启发性的，详情看代码吧TAT
#include<cstring> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstdio> #include<cmath> #include<queue> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 2005 #define ll long long using namespace std; int a[maxn],b[maxn],c[maxn],sum[maxn],s,n,m,l,r,ans,rest; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } bool dfs(int dep,int last){ if (dep<=0) return 1; if (rest+sum[dep]>s) return 0; rep(i,last,n) if (c[i]>=b[dep]){ c[i]-=b[dep]; if (c[i]<b[1]) rest+=c[i]; if (b[dep]==b[dep-1]) {if (dfs(dep-1,i)) return 1;} else {if (dfs(dep-1,1)) return 1;} if (c[i]<b[1]) rest-=c[i]; c[i]+=b[dep]; } return 0; } bool jud(int mid){ rep(i,1,n) c[i]=a[i]; rest=0; return dfs(mid,1); } int main(){ // freopen("in.txt","r",stdin); n=read(); rep(i,1,n) a[i]=read(),s+=a[i]; m=read(); rep(i,1,m) b[i]=read(); sort(a+1,a+1+n); sort(b+1,b+1+m); rep(i,1,m) sum[i]=sum[i-1]+b[i]; while (sum[m]>s) m--; l=0; r=m; while (l<r){ int mid=(l+r)/2; if (jud(mid+1)) l=mid+1; else r=mid; } printf("%d ",l); return 0; }