18分蒟蒻求助
  • 板块P1120 小木棍
  • 楼主int__main
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/28 15:08
  • 上次更新2023/11/3 00:43:00
查看原帖
18分蒟蒻求助
752792
int__main楼主2023/8/28 15:08

6个点AC,剩下有的WA有的TLE,调了半天都没变化,望哪位大佬指点一下

#include<cstdio>
#include<cstring>
int n,a[70],sum=0;
int p[10],num;
int len,N,minn=114514;
bool used[70],stop=false;
inline int Decomposition(int s,int arr[]){
	int cnt=0;
	arr[cnt++]=1;
	for(int i=2;i<=s;i++){
		if(s%i==0)arr[cnt++]=i;
	}
	if(s>1)arr[cnt++]=s;
	return cnt;
}
inline long long read_integer(){
	char s;
	bool p_n=true;
	long long val=0;
	while(1){
		s=getchar();
		if(s=='-')p_n=false;
		else if(s>='0'&&s<='9')val=val*10+s-'0';
		else break;
	}
	if(!p_n)val*=-1;
	return val;
}
inline void dfs(int val,int th){
	if(stop)return;
	if(val==len){
		if(th==N){
			printf("%d",len);
			stop=true;
			return;
		}
		else
			dfs(0,th+1);
		return;
	}
	for(int i=0;i<n;i++){
		if((!used[i])&&val+a[i]<=len){
			used[i]=true;
			dfs(val+a[i],th);
			used[i]=false;
		}
	}
}
int main(){
	memset(used,0,sizeof(used));
	n=read_integer();
	for(int i=0;i<n;i++){
		a[i]=read_integer();
		sum+=a[i];
		if(a[i]<minn)minn=a[i];
	}
	puts("good");
	num=Decomposition(sum,p);
	for(int i=0;i<num;i++){
		if(p[i]<minn)continue;
		len=p[i];
		N=sum/p[i];
		dfs(0,1);
		if(stop)break;
	}
	return 0;
} 
2023/8/28 15:08
加载中...