蒜头君手上有一些小木棍,它们长短不一,蒜头君想用这些木棍拼出一个等边三角形,并且每根木棍都要用到。 例如,蒜头君手上有长度为 12334根木棍,他可以让长度为12 的木棍组成一条边,另外 2 根分别组成 2 条边,拼成一个边长为 3 的等边三角形。蒜头君希望你提前告诉他能不能拼出来,免得白费功夫。

输入格式

首先输入一个整数 n (3≤n≤20),表示木棍数量,接下来输入 n 根木棍的长度 pi ​ (1≤ pi ≤10000)。

输出格式

如果蒜头君能拼出等边三角形,输出”yes”,否则输出”no”。

样例输入1

1
2
5 
1 2 3 4 5

样例输出1

1
yes

样例输入2

1
2
4 
1 1 1 1

样例输出2

1
no

分析

这道题目又是一道选择的题目,我们有三种选择的方法。

  • 1:我们把这根木棍放到第一条边上。

  • 2:我们把这根木棍放到第二条边上。

  • 3:我们把这根木棍放到第三条边上。

对应三个dfs。与此同时处理好递归出口的问题就好了。

接下来我要说说这道题目的不同。我们对于这道题目我们可以进行一定的剪枝。

  • 1:当平均值不是整数的时候我们就可以直接判定是无法拼成等边三角形的。

  • 2:当其中的一个木棍长度大于平均值,也是无法拼成等边三角形的。

  • 3:最优性剪枝,当你搜索到答案的时候,就结束所有的递归。

这个时候是不是发现其实优化也不是那么难?其实更多的优化都是我们自己可以想出来的,一个看似简单的优化,会给你的代码提高极大的运行效率。

代码

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
#include<iostream>
using namespace std;

int n; // stick num
int s[20] = {0}; //stick length
int flag = 0;
int Length = 0; //正确的长度

void dfs(int deep, int tri[]) {
if(flag == 1 || deep > n) return; //剪枝
if(tri[0] > Length || tri[1] > Length || tri[2] > Length) //剪枝
return;
if(deep == n){ //木棒用完
if(tri[0] == tri[1] && tri[0] == tri[2]){
//Wrong:tri[0] == tri[1] == tri[2]
flag = 1;
}
return;
}
for(int i = 0; i < 3; i++){ //枚举当前木棒的三个去向
tri[i] += s[deep];
dfs(deep+1, tri);
tri[i] -= s[deep];
}
}

int main() {
int tri[3] = {0}; //每条边的长度
int sumLength = 0;
cin >> n;
for(int i = 0; i < n; i++){
cin >> s[i];
sumLength += s[i];
}
Length = sumLength/3; //应该的长度
if(sumLength % 3 != 0) //优化
cout << "no" << endl;
else{
dfs(0,tri);
if(flag == 1) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}

标程

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
#include<iostream>
using namespace std;

int l[30];
int n, sum = 0;
bool ok = 0;

void dfs(int id, int l1, int l2, int l3){
if(l1 > sum || l2 > sum || l3 > sum){
return;
}
if(ok){
return;
}
if(id == n){
if(l1 == l2 && l1 == l3){
ok == 1;
}
return;
}
dfs(id+1, l1+l[id], l2, l3);
dfs(id+1, l1, l2+l[id], l3);
dfs(id+1, l1, l2, l3+l[id]);
}

int main(){
int ca;
cin >> n;
for(int i = 0; i < n; i++){
cin >> l[i];
sum += l[i];
}
if(sum % 3 != 0){
cout << "no" << endl;
return 0;
}
sum /= 3;
dfs(0, 0, 0, 0);
if(ok) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}

更新记录

  • 2018年02月20日 完成题解