2022绍兴小学-----问题 D: 三角形(triangle) 题解

题目

问题 D: 三角形(triangle)

题目描述

小魏有 3n 根颜色两两不同的木棍，第i根的长度为a[i]。
小魏想把这3n根木棍分成n组，每组三根，并且同一组的三根木棍可以组成一个三角形。
小魏想知道他有多少种不同的分组方案。认为两个分组方案是不同的,当且仅当两种方案组出来的三角形是不同的。

输入

第一行一个整数n。
第二行3*n个整数a[i]。

输出

一行一个整数，表示方案数。

样例输入

2
3 4 5 10 11 12

样例输出

1

提示

对于20% 的数据，n=1；
对于50% 的数据，n≤3；
对于70% 的数据，n≤4；
另有10% 的数据，所有a[i] 全部相等；
对于所有数据，1≤n≤5, 1≤a[i] ≤100。

题解

考试的时候来不及了，打了表，然后只有20分……
直接深搜即可。

#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(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	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;
}