求问
查看原帖
求问
1114874
maniubi123楼主2023/11/4 09:36

这样写的话87pts

#include<bits/stdc++.h>
#define ll long long
#define un unsigned
using namespace std;
int a[105],v[105],n,len,cnt;
bool dfs(int stick,int cab,int last){
	if(stick>cnt) return true;
	if(cab==len) return dfs(stick+1,0,1);
	int fail=0;
	for(int i=last;i<=n;i++){
		if(!v[i]&&cab+a[i]<=len&&fail!=a[i]){
			v[i]=1;
			if(dfs(stick,cab+a[i],i+1)) return true;
			fail=a[i];
			v[i]=0;
			if(cab==0||cab+a[i]==len) return false;
		}
	}
	return false;
}
int main(){
	while(cin>>n&&n){
		int sum=0,val=0;
		for(int i=1;i<=n;i++){
			a[i]=read();
			sum+=a[i];
			val=max(val,a[i]);
		}
		sort(a+1,a+n+1);
		reverse(a+1,a+n+1);
		for(len=val;len<=sum;len++){
			if(sum%len) continue;
			cnt=sum/len;
			memset(v,0,sizeof(v));
			if(dfs(1,0,1)) break;
		}
		cout<<len<<endl;
	}
	return 0;
}

加了快读之后就A了,有什么不加快读A掉的剪枝思路么?

2023/11/4 09:36
加载中...