题目
问题 D: 三角形(triangle)
题目描述
小魏有 3n 根颜色两两不同的木棍，第i根的长度为a[i]。
小魏想把这3n根木棍分成n组，每组三根，并且同一组的三根木棍可以组成一个三角形。
小魏想知道他有多少种不同的分组方案。认为两个分组方案是不同的,当且仅当两种方案组出来的三角形是不同的。
输入
第一行一个整数n。
第二行3*n个整数a[i]。
输出
一行一个整数，表示方案数。
样例输入
样例输出
提示
对于20% 的数据，n=1；
对于50% 的数据，n≤3；
对于70% 的数据，n≤4；
另有10% 的数据，所有a[i] 全部相等；
对于所有数据，1≤n≤5, 1≤a[i] ≤100。
题解
考试的时候来不及了，打了表，然后只有20分……
直接深搜即可。
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
| #include <bits/stdc++.h>
using namespace std;
int n,a[22],b[22];
int maxn;
void dfs(int x){
if (x == n+1){
maxn++;
return;
}
if (b[x]){
dfs(x+1);
return;
}
for (int y = x+1; y <= n; y++){
if (b[y] == 0){
for (int z = y+1; z <= n; z++){
if (b[z] == 0){
if (a[x]+a[y] > a[z]){
b[x] = b[y] = b[z] = 1;
dfs(x+1);
b[x] = b[y] = b[z] = 0;
}
}
}
}
}
}
int main(){
scanf("%d",&n);
n = 3*n;
for (int i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
sort(1+a,1+a+n);
dfs(1);
printf("%d",maxn);
return 0;
}
|
