HDU-4277 USACO ORZ 题解

题目大意

给你n条边，求将这些边用完的情况下，能组成多少个不同的三角形。

解题思路

刚开始还觉得挺简单的。

就一个暴力dfs加set去重。

但是直接TLE了，后面加了剪枝还在T。。

因为不怎么会用自定义类型的set，所以就用了string来去重。

结果看了题解，发现就是这里导致的T。

（string太慢了。。

然后就在想，怎么让他去重。

卡了我好久。

还好这里的边长度不大，所以只需要用一个类字符串的形式来去重。

剪枝的话，因为最大值是不能大于等于三边总和的2/3的，所以按照这个条件来剪枝。

在去重的时候，还需要三条边按照升序或者降序来去重，不然答案会重复。

完整代码

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
int num[20], n, sum;
set<ll>s;

void dfs(int a,int b,int c,int cnt) {
	if (max(max(a,b),c)*2>=sum)	return;
	if (cnt == n ) {
		if (a > b || a > c || b > c ) {
			return;
		}
		if (a + b > c && a + c > b && b + c > a) {
			ll ans = (((a * 10000) + b) * 10000) + c;
			s.insert(ans);
		}
		return;
	}
	dfs(a + num[cnt], b, c, cnt + 1);
	dfs(a, b + num[cnt], c, cnt + 1);
	dfs(a, b, c + num[cnt], cnt + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n;
		sum = 0;
		s.clear();
		for (int i = 0; i < n; i++)	cin >> num[i], sum += num[i];
		dfs(0,0,0,0);
		cout << s.size() << endl;
	}
}