HDU 4277 USACO ORZ （暴力搜索+set去重）

枚举3^15种情况，不同的三角形用set去重。

先让所有段加入一条边，在逐个移动至另外两边，枚举所有的情况

卡着时间过去的...........

include <cstdio>   
#include <cmath>   
#include <iostream>   
#include <algorithm>   
#include <cstring>   
#include <set>   
using namespace std;  
int a[22];  
int n;  
int sum,ans,flag;  
struct node {  
    int x,y,z;  
    bool operator < (const node &a) const {  
        if(a.x != x) return a.x < x;  
        if(a.y != y) return a.y < y;  
        return a.z < z;  
    }  
};  
  
set <node> s; //自定义set   
void init() {  
    s.clear();  
}  
  
void dfs(int v0,int v1,int v2,int i) {  
    if(i >= n) return ;  
    if(v0 + v1 > v2 && v0 + v2 > v1  && v1 + v2 > v0) {  
        int a1,a2,a3,tmp;  
        node t;  
        a1 = v0;  
        a2 = v1;  
        a3 = v2;  
        if (a2 > a3) {  
            swap(a2,a3);  
        }  
        if (a1 > a2) {  
            swap(a1,a2);  
        }  
        if (a2 > a3) {  
            swap(a2,a3);  
        }  
        t.x = a1;  
        t.y = a2;  
        t.z = a3;  
        s.insert(t);  
    }  
    //每个i，三种选择   
    if(v0 + v1 - a[i] > v2 + a[i]) dfs(v0 - a[i],v1,v2 + a[i] ,i+1);  
    if(v0 + v2 - a[i] > v1 + a[i]) dfs(v0 - a[i],v1 + a[i],v2, i+1);  
    dfs(v0,v1,v2,i+1);  
}  
  
int main() {  
    int T;  
    cin >> T;  
    while(T --) {  
        init();  
        scanf("%d",&n);  
        sum = 0;  
        for(int i=0; i<n; i++) {  
            scanf("%d",&a[i]);  
            sum += a[i];  
        }  
        dfs(sum,0,0,0);  
        printf("%d\n",s.size());  
    }  
    return 0;  
}  

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
int a[22];
int n;
int sum,ans,flag;
struct node {
    int x,y,z;
    bool operator < (const node &a) const {
        if(a.x != x) return a.x < x;
        if(a.y != y) return a.y < y;
        return a.z < z;
    }
};

set <node> s; //自定义set
void init() {
    s.clear();
}

void dfs(int v0,int v1,int v2,int i) {
    if(i >= n) return ;
    if(v0 + v1 > v2 && v0 + v2 > v1  && v1 + v2 > v0) {
        int a1,a2,a3,tmp;
        node t;
        a1 = v0;
        a2 = v1;
        a3 = v2;
        if (a2 > a3) {
            swap(a2,a3);
        }
        if (a1 > a2) {
            swap(a1,a2);
        }
        if (a2 > a3) {
            swap(a2,a3);
        }
        t.x = a1;
        t.y = a2;
        t.z = a3;
        s.insert(t);
    }
    //每个i，三种选择
    if(v0 + v1 - a[i] > v2 + a[i]) dfs(v0 - a[i],v1,v2 + a[i] ,i+1);
    if(v0 + v2 - a[i] > v1 + a[i]) dfs(v0 - a[i],v1 + a[i],v2, i+1);
    dfs(v0,v1,v2,i+1);
}

int main() {
    int T;
    cin >> T;
    while(T --) {
        init();
        scanf("%d",&n);
        sum = 0;
        for(int i=0; i<n; i++) {
            scanf("%d",&a[i]);
            sum += a[i];
        }
        dfs(sum,0,0,0);
        printf("%d\n",s.size());
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：poj 2109 Power of Cryptography(用double避开高精度)
下一个：hdu1421 搬寝室