记录编号	196939	评测结果	AAAAAAAAAAAA
题目名称	栅栏的木料	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2015-10-22 21:40:09	内存使用	0.33 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int SIZEN=60,SIZER=1040;
int N,R,board[SIZEN],rail[SIZER],sb=0,sr=0;
int pos[SIZER]={0},pre[SIZER]={0};
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&board[i]);
		sb+=board[i];
	}
	scanf("%d",&R);
	for(int i=1;i<=R;i++)scanf("%d",&rail[i]);
}
bool dfs(int now,int sum)
{
	if(now<1) return 1;
	if(sum>sb-sr) return 0;
	bool ok=0;
	int st=1;
	if(rail[now]==rail[now+1]) st=pos[now+1];
	for(int i=st;i<=N;i++)
	{
		if(board[i]>=rail[now])
		{
			board[i]-=rail[now];
			int tem=sum;
			pos[now]=i;
			if(board[i]<rail[1]) tem=sum+board[i];
			if(dfs(now-1,tem)) ok=1;
			board[i]+=rail[now];
			pos[now]=0;
			if(ok==1) return 1;
		}
	}
	return 0;
}
bool check(int x)
{
	sr=pre[x];
	if(dfs(x,0)) return 1;
	else return 0;
}
bool cmp(int a,int b)
{
	return a>b;
}
void work()
{
	int l=0,r=R;
	sort(rail+1,rail+R+1);
	sort(board+1,board+1+N);
	for(int i=1;i<=R;i++) pre[i]=pre[i-1]+rail[i];
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid;
		//cout<<mid<<endl;
	}
	if(!check(r)) r--;
	printf("%d",r);
}
int main()
{
	freopen("fence8.in","r",stdin);
	freopen("fence8.out","w",stdout);
	read();
	work();
	return 0;
}