链接:
https://www.acwing.com/problem/content/169/
题意:
乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序,帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
注意: 数据中可能包含长度大于50的木棒,请在处理时忽略这些木棒。
思路:
剪枝, 优先从大到小, 同时记录上一次选的不符号, 下一次就不要选了.
从0开始,或者可以刚好选满的情况,无法拼出全部直接返回.
代码:
#include <bits/stdc++.h>
using namespace std;
int Vis[100], a[100];
int sum, mmax;
int n, nn, cnt, len;
bool Dfs(int stick, int tmp, int las)
{
if (stick > cnt)
return true;
if (tmp == len)
return Dfs(stick+1, 0, 1);
int lastlen = 0;
for (int i = las;i <= n;i++)
{
if (Vis[i] == 0 && tmp+a[i] <= len && a[i] != lastlen)
{
Vis[i] = 1;
if (Dfs(stick, tmp+a[i], i+1))
return true;
lastlen = a[i];
Vis[i] = 0;
if (tmp == 0 || tmp+a[i] == len)
return false;
}
}
return false;
}
int main()
{
while(scanf("%d", &nn) && nn)
{
sum = mmax = 0;
int v;
n = 0;
for (int i = 1; i <= nn; i++)
{
scanf("%d", &v);
if (v > 50)
continue;
a[++n] = v;
sum += a[n];
mmax = max(mmax, a[n]);
}
sort(a+1, a+1+n, greater<int>());
for (int i = mmax;i <= sum;i++)
{
if (sum%i)
continue;
memset(Vis, 0, sizeof(Vis));
cnt = sum/i;
len = i;
if (Dfs(1, 0, 1))
break;
}
printf("%d\n", len);
}
return 0;
}