资深守护
#include <iostream>
using namespace std;
bool flag[66];
long long a[66],b[66],c[66],n;
int main()
{
long long sum=0,max=0;
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
if (max<a[i])
max=a[i];
}
for (int i=max;i<=sum;i++)
{
if (sum%i==0)
{
cout<<i;
break;
}
}
return 0;
}
资深天翼
总得来说就是剪枝DFS:枚举最小长度,进行拼凑.
几个剪枝:
-
枚举最小长度时(设为len),可得:min(小木棍长度)<=len<=小木棍总长,同时(总长 mod len=0).
-
当每次接入小木棍后,大木棍未达到要求长度时,下一个接入的小木棍取比刚刚接入的小木棍短的小木棍.
-
当一个小木棍接入后,当前处理的大木棍刚好达到要求的长度的话,没必要用更多的小木棍代替这个刚接入的小木棍,因为更短的小木棍比它有更大的适用性(所以把它们留在后面用必定比接入这里更好).
- 当处理完一个大木棍之后,接入下一个大木棍的第一根小木棍用剩下的最长的小木棍.
几个处理:
-
枚举最小长度时由小到大枚举,找到第一个后直接输出就可以HALT了.
- 将所有木棍由大到小排序,以便剪枝.
注意事项:
题目说:"直到每段的长都不超过50",所以去掉超过50的小木棍
缔造者之神
1
资深光能
void dfs(int ans,int sum,int goal,int now){
if(sum*goal==maxn){printf("%d\n",goal); exit(0);}
if(maxn-ans<a[cnt])return;
if(ans==goal){dfs(0,sum+1,goal,1); return;}
for( int i=now;i<=cnt;i++)
if(!use[i] && ans+a[i]<=goal){
use[i]=1;
dfs(ans+a[i],sum,goal,i+1);
use[i]=0;
if(ans+a[i]==goal || ans==0)break;
while(a[i]==a[i+1])i++;
}
缔造者
1
初级光能
1
