萌新求助
查看原帖
萌新求助
382274
暗影之梦楼主2022/5/13 09:24

在loj上做的这一题,现在dfs程序一直无法结束但又不完全像是死循环,求调

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,a[61],sum,num,l,maxa,nmax;
bool vis[61];
bool cmp(int x,int y)
{
	return x>y;
}
bool dfs(int i,int len,int st)
{
//	cout<<i<<" "<<len<<" "<<st<<endl;
	if(i>num) return 1;
	if(len==l) return dfs(i+1,0,1);
	for(int j=st;j<=n;j++)
	{
		if(vis[j]) continue;
		if(len+a[j]>l) continue;
//		cout<<i<<" "<<a[i]<<endl;	
		vis[j]=1; 
		if(dfs(i,len+a[j],j)) 
		{
			return 1;
		}
		vis[j]=0;
		if(len==0) return 0;
		if(len+a[j]==l) return 0;
	}
	return 0;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
		maxa=max(a[i],maxa);
	}
	for(int i=2;i*i<=n;i++)
	{
		if(sum%i==0)
		{
			nmax=sum/i;
			break;
		}
	}
	sort(a+1,a+n+1,cmp);
	for(int i=nmax;i>=1;i--)
	{
		if(sum%i!=0)
		{
			continue;
		}
		memset(vis,0,sizeof(vis));
		l=sum/i;
		num=i;
//		cout<<l<<" "<<num<<endl;
		if(l<maxa) continue;
		if(dfs(1,0,1))
		{
			scanf("%lld",l);
			break;
		}
	}
	return 0;
} 
2022/5/13 09:24
加载中...