AcWing 167. 木棒-y总视频详细注释
原题链接
中等
作者:
双水
,
2024-03-27 19:24:08
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
const int N=70;
int n;
int w[N];//表示每一根木棍的长度
bool st[N];//表示每一根木棍有没有用过
int sum;//当前木棍的总长度
int len;//当前枚举的长度
bool dfs(int u,int cur,int start)
//u表示当前枚举到了第几根长木棍,cur表示当前拼的长木棍的长度,start当前长木棍的下标
{
if(u*len==sum) return true;//枚举的所有方案都满足
if(cur==len) return dfs(u+1,0,0);//当前的木棍已经拼好了,枚举下一根
for(int i=start;i<n;i++)
{
if(st[i]) continue;//如果当前的小木棍已经用过的,就continue
//判断当前木棍能不能用
if(cur+w[i]<=len)
{
st[i]=true;
//如果可以用,进入递归
if(dfs(u,cur+w[i],i+1)) return true;
st[i]=false;
}
//剪枝
if(!cur||cur+w[i]==len) return false;
//剪枝
int j=i+1;
while(j<n&&w[i]==w[j]) j++;
i=j-1;//把所有和i长度相等的跳过
}
return false;
}
int main()
{
while(cin>>n,n)
{
sum=len=0;
for(int i=0;i<n;i++)
{
cin>>w[i];
sum+=w[i];
len=max(len,w[i]);//从最长的开始搜索
}
//从大到小排序
sort(w, w + n, greater<int>());
memset(st,0,sizeof st);//清空数组
while(true)//不会死循环,因为绝对有答案,也就是将所有的小木棍并在一起
{
if(sum%len==0&&dfs(0,0,0))//因为总的木棍的个数是整数,所以总的木棍长度必须能够整除当个木棍的长度,sum%len==0
{
cout<<len<<endl;
break;
}
len++;
}
}
return 0;
}