HDU 4277 – USACO ORZ [搜索]

点击打开HDU题目链接

题意

给定N根木棍,要求用N根木棍(全部用上)组成一个三角形,问能组成多少种不同的三角形,只要有一条编长不同即视为不同三角形。

分析

比赛的时候光想着二进制枚举了,得需要(2^15)^2的复杂度,肯定会超时,思维真是太呆滞了!其实因为每条木棍都会用上,那么直接搜索这条木棍属于那条边,直接DFS就可以可,复杂度是3^15,再用hash加set判断重复即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 20, inf = 177777;
int n, v[maxn];
set<ll> s;

void dfs(int d, int a, int b, int c) {
    if(d == n) {
        if(a && b && c && a<=b && b<=c && a+b>c)
            s.insert(inf * inf * a + inf * b + c);
        return;
    }
    dfs(d+1, a+v[d], b, c);
    dfs(d+1, a, b+v[d], c);
    dfs(d+1, a, b, c+v[d]);
}

int main() {
    int T; scanf("%d", &T);
    while(s.clear(), T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", v + i);
        dfs(0, 0, 0, 0);
        printf("%d\n", s.size());
    }
    return 0;
}

欢迎留言