USACOORZHDU_4277DFS+STL+枚举算法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4277

/* Author: Bob Lee Date: 2012-09-15 Problem Description: 给定n个木棍，求可以组成的不同三角形的数量，最多15根木棍。 Solution Approach: 使用深度优先搜索（DFS）进行枚举，结合STL中的set容器来去重。 每种组合的三条边按从小到大排序，计算一个哈希值，如果该哈希值不在set中，则将其加入set。 注意：不能使用sort函数，否则会导致超时（TLE）。 */ #include #include #include #include using namespace std; #define MAXN 16 set myset; int n; int data[MAXN]; int m; int sum; void dfs(int num, int x1, int x2, int x3) { if (num > n) return; if (x1 + x2 > x3 && x2 + x3 > x1 && x3 + x1 > x2) { int a[3] = {x1, x2, x3}; if (a[0] > a[1]) swap(a[0], a[1]); if (a[0] > a[2]) swap(a[0], a[2]); if (a[1] > a[2]) swap(a[1], a[2]); long long hash = a[0] + a[1] * sum + a[2] * sum * sum; if (myset.find(hash) == myset.end()) { m++; myset.insert(hash); } } if (x3 - data[num] + x2 > x1 + data[num]) dfs(num + 1, x1 + data[num], x2, x3 - data[num]); if (x3 - data[num] + x1 > x2 + data[num]) dfs(num + 1, x1, x2 + data[num], x3 - data[num]); dfs(num + 1, x1, x2, x3); } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); m = 0; sum = 0; myset.clear(); for (int i = 1; i <= n; i++) { scanf("%d", &data[i]); sum += data[i]; } dfs(1, 0, 0, sum); printf("%d\n", m); } return 0; }