题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//从小到大枚举答案
// 依次拼接每根长度为len的木棍
// 剪枝1:优化搜索顺序,从小到大枚举,尽可能早的触发剪枝
// 剪枝2:排除多余方案,每一根长木棍的内部的小木棍编号递增,排除多个排列组合
// 剪枝3:可行性剪枝:
// 1.匹配失败后,跳过与当前长度相等的其他木棍
// 2.第一个未被使用过的木棍若作为新长木棍的第一根无解则回溯,因为每根木棍都要被用到并且编号从小到大
// 3若当前小木棍加上后,当前长木棍满足要求长度但是剩余木棍无法拼凑,因为如果它满足要求则在未来拼凑一定也能拼成,则回溯
#include<bits/stdc++.h>
using namespace std;
const int N = 70;
int w[N], sum, len, n;
bool vis[N];
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(vis[i])continue; //当前小木棍已用过
if(cur + w[i] <= len)
{
vis[i] = true;
if(dfs(u, cur + w[i], i + 1)) return true;
vis[i] = false;//恢复现场
}
//如果这根小木棍没有在上面匹配成功,回溯时在此进行三个可行性剪枝
//可行性剪枝2, 3
//cur 为0 代表这是第一个未被使用过的小木棍作为新长木棍的一根无解
//cur + w[i] == len 代表最后一根小木棍
if(! cur || cur + w[i] == len) return false;
//可行性剪枝1
int j = i + 1;
while(j < n && w[i] == w[j]) j ++;
i = j - 1;;
}
return false;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
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]);
}
//剪枝1
sort(w, w + n, greater<int>());
memset(vis, 0, sizeof vis);
while(1)
{
if(sum % len == 0 && dfs(0, 0, 0))
{
cout << len << '\n';
break;
}
len ++;
}
}
}
blablabla