poj-2362

//132K  141MS   C++ with beginSearchPos
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

int cmp(const void* a,const void* b)  //降序  
{  
    return *(long long*)b-*(long long*)a;  
}

long long fourEdgeLength[4];

long long lengthSum;
long long edgeMaxLength;

int caseNum;

bool flag;

long long sticks[21];
int stickNum;

char visited[21];

void dfs(int completeLineNum, int leftLength, int beginSearchPos) {
    if (flag) {
        return;
    }

    if (completeLineNum == 3) {
        flag = 1;
        return;
    }

    for (int i = beginSearchPos; i <= stickNum; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            if (sticks[i] == leftLength) {
                completeLineNum++;
                if (completeLineNum == 3) {
                    flag = 1;
                    return;
                } else {
                    dfs(completeLineNum, edgeMaxLength, 1);
                }
            } else if (sticks[i] < leftLength) {
                dfs(completeLineNum, leftLength - sticks[i], i + 1);
            }
            visited[i] = 0;
            if (flag) {
                return;
            }
        }
    }
}

int main() {
    scanf("%d", &caseNum);
    for (int i = 1; i <= caseNum; i++) {
        flag = 0;
        lengthSum = 0;
        memset(sticks, 0, sizeof(sticks));
        memset(visited, 0, sizeof(visited));
        scanf("%d", &stickNum);
        memset(fourEdgeLength, 0, sizeof(fourEdgeLength));
        int MAX = -1;
        for (int j = 1; j <= stickNum; j++) {
            scanf("%lld", &sticks[j]);
            lengthSum += sticks[j];
            MAX = MAX > sticks[j] ? MAX: sticks[j];
        }
        qsort(sticks, stickNum , sizeof(long long), cmp);
        edgeMaxLength = lengthSum/4;
        if (lengthSum%4 || sticks[0] > edgeMaxLength) {
            printf("no\n");
            continue;
        }

        // printf("edgeMaxLength %lld\n", edgeMaxLength);
        dfs(0, edgeMaxLength, 1);
        if (flag) {
            printf("yes\n");
        } else {
            printf("no\n");
        }
    }
}

经典的dfs剪枝题，一般一道题如果使用DFS做的话，都会多少的考察剪枝， 这里将stick预先从大到小排序是关键，这样在后面每次dfs时 不必遍历所有的stick遍历，

只需遍历边上一次选择的stick短的即可（很重要，每次都从1开始遍历stick会TLE）