社区讨论

大佬帮我看看怎么优化

学术版参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo8xpiib
此快照首次捕获于
2023/10/28 02:16
2 年前
此快照最后确认于
2023/10/28 02:16
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int len,n,a[100],t[100],start=0,sum=0;
void dfs(int now,int k)
{
	if(now==n+1)
	{
		int ok=0;
		for(int i=1;i<=n;i++)
		{
			if(t[i]==len)
			{
				ok++;
			}
			else
				break;
		}
		if(ok==k)
		{
			cout<<len;
			exit(0);
		}
	}
	else
	{
		for(int i=1;i<=k;i++)
		{
			if(a[now]+t[i]<=len)
			{
				t[i]+=a[now];
				dfs(now+1,k);
				t[i]-=a[now];
			}
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		start=max(start,a[i]);
		sum+=a[i];
	}
	sort(a+1,a+n+1);
	for(len=start;len<=sum/2;len++)
	{
		if(sum%len==0)
		{
			int k=sum/len;
			dfs(1,k);
		}
	}
	cout<<sum;
	return 0;
}
题号P1120 本来想看题解,结果发现我的思路比较清奇(或者是我没找到),以至于我不知道怎么给这个dfs剪枝了。代码应该没问题,但是27分,其他全TLE了.....
求助

回复

0 条回复,欢迎继续交流。

正在加载回复...