hdu 1518 Square|ZOJ 1909|POJ 2362(dfs+剪定)

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=1518
标题:あなたにn本の木の棒をあげて、光のすべての木の棒で正方形につづることができるかどうかを聞きます.
dfs
枝切り:
       1、三辺を検索すると、四辺目も確定します.このとき解が見つかり、検索を停止できます.
       2、木の棒は1本ずつ使うので、1本目の端を探すときに1本目の木の棒をこの辺の最初の木の棒として直接持つことができます.
       3、検索が完了した後、次の検索の数が現在と同じであれば、次の異なる数を探して検索します.
hdu上 46 MSは第1版に絞った. \(≧▽≦)/

#include <cstdio>
#include <cstring>
#include <functional>
#include <algorithm>
#define N 25
using namespace std;
int ave, n;
bool flag;
bool vis[N];
int a[N];

void dfs( int sum, int k, int cnt) {
    if(flag) return;
    if(cnt==3) {
        flag = true;
        return;
    }
    for(int i=k+1; i<=n; i++)
        if(!vis[i]&&!flag&&sum+a[i]<=ave) {
            vis[i] = 1;
            if(sum+a[i]==ave) dfs(0,0,cnt+1);
            else  dfs(sum+a[i],i,cnt);
            vis[i] = 0;
            if(sum==0) break;
            while(a[i]==a[i+1]) i++;
        }
}

int main() {
    int T, i, s;
    scanf("%d",&T);
    while(T--) {
        s = 0;
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        for(i=1; i<=n; i++) {
            scanf("%d",a+i);
            s +=a[i];
        }
        sort(a+1,a+n+1,greater<int>());
        flag  = false;
        if(s%4==0) {
            ave = s/4;
            dfs(0,0,0);
        }
        if(flag) printf("yes
");
        else printf("no
");
    }
    return 0;
}