还能剪枝吗
  • 板块学术版
  • 楼主pencil
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/8/22 21:22
  • 上次更新2023/11/6 19:38:22
查看原帖
还能剪枝吗
137723
pencil楼主2020/8/22 21:22
#include<bits/stdc++.h>
using namespace std;
bool cmd(int a,int b){
	return a<b;
}
int mid;int a[60],b[1034],i,n,m,i2,ji[1034],qian[1034],zong,fei;
bool dfs(int start,int x){
	if(zong-fei<b[mid])  return 0;
	if(x==0) return true;
	int i,flag;
	for(i=start;i<=n;i++){
		if(a[i]>=b[x]){
			a[i]-=b[x];
			if(a[i]<a[1])
			fei+=a[i];
			if(b[x]==b[x-1])
			flag=dfs(i,x-1);
			else
			flag=dfs(1,x-1);
			if(a[i]<a[1])
			fei-=a[i];
			a[i]+=b[x];
			if(flag)  return 1;
		}
	}
	return 0;
}
int main(){
	int big;
	cin>>n;
	for(i=1,big=-1;i<=n;i++) cin>>a[i],big=max(big,a[i]),zong+=a[i];
	cin>>m;
	for(i=1;i<=m;i++) cin>>b[i];
	sort(a+1,a+n+1,cmd);
	sort(b+1,b+m+1,cmd);
	for(i=m;i!=0;i--) if(b[i]<=big) break;
	m=i;
	int r=m,l=1,shu=0;
	for(;l<=r;){
		mid=(l+r)/2;
		if(dfs(1,mid))
		l=mid+1,shu=mid;
		else{
			r=mid-1;
		}
	}
	cout<<shu;
	return 0;
}

P1528TLE了QWQ

2020/8/22 21:22
加载中...