链接:
Sticks

听说是一道经典的深搜剪枝题,果然剪不够就TLE到要哭……
题意大概是,给你n根木棍和各自的长度,要你把他们拼成m根木棍,m<=n。

0.枚举可能的长度进行尝试,首先可能的长度一定大于等于最长的木棍,另外一定是所有木棍长度和的因子
1.将木棍排序,设置一个数组表示是否使用过这根木棍,并从长到短来进行衔接
2.如果在某次查找中,某根木棍不可取,那么与其长度相同的也可以跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <fstream>
using namespace std;
int maxn = 0, sum = 0, minn = 0;
//maxn是最长的木棍,sum是给出的木棍的长度之和,minn是最终可以拼出的最短长度
int n,m,mm;
int sticks[70],chose[70];
int dfs(int x, int sur, int curi, int left)
{//x是当前要拼的长度,sur是还剩余多少拼成x,curi是当前拼到哪一个木棍,left是还有多少木棍没有使用
if(sur==0)
{//如果已经拼到x了,有两种可能,木棍用完说明已经得到最小长度,木棍没用完的话还要用剩下的木棍拼接
if(left==0) return 1;
int i = n-2;//这里不应该循环查找!因为所有木棍都要用上,所以不存在跳过某一根的情况
while(chose[i]) i--;
chose[i]=1;
if(dfs(x, x-sticks[i], i-1, left-1)) return 1;
chose[i]=0;
return 0;
}
if(sur<0) return 0;//如果木棍长度超出则返回上层函数
for (int i = curi; i >= 0; i--)
{
if(chose[i]) continue;//如果已经使用过就看下一根
chose[i]=1;
if(dfs(x, sur-sticks[i], curi-1, left-1)) return 1;
chose[i]=0;
while(sticks[i]==sticks[i-1]) i--;//既然用i不行,那么用和i一样长的肯定也不行咯
}
return 0;
}
int main(int argc, char const *argv[])
{
while(scanf("%d",&n)&&n!=0)
{
maxn = 0, sum = 0, minn = 0;
memset(chose, 0, sizeof(chose));
for (int i = 0; i < n; ++i)
{
scanf("%d", &sticks[i]);
sum+=sticks[i];
if(sticks[i] > maxn) maxn = sticks[i];
}
sort(sticks,sticks+n);
chose[n-1]=1;//第n-1根首先就用了
for (int i = maxn; i < sum; ++i)
{
if(sum%i==0)//可以拼出的长度一定是sum的因子
{
if(dfs(i, i-sticks[n-1], n-2, n-1))
{
minn=i;
break;
}
}
}
if(minn==0) minn=sum;//如果拼到sum还不行那就当然只能是sum了
printf("%d\n",minn);
}
return 0;
}