1518.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 62 行

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int stick[22];
int num,total,ave;
bool finish,use[22];
bool cmp(int a,int b){
    return a>b;
}
void dfs(int start,int sok,int slen){
    if(sok==3){
        finish=true;
        return;
    }
    for(int i=start;i<num&&!finish;i++){
        if(!use[i]){
            if(slen+stick[i]==ave){
                use[i]=true;
                dfs(0,sok+1,0);
                use[i]=false;
            }
            else if(slen+stick[i]<ave){
                use[i]=true;
                dfs(i+1,sok,slen+stick[i]);
                use[i]=false;
            }
        }
     }
    return;
}
void main()
{
    int testcase;
    cin>>testcase;
    while(testcase--){
        memset(stick,0,sizeof(stick));
        memset(use,0,sizeof(use));
        cin>>num;total=0;
        for(int i=0;i<num;i++){
            cin>>stick[i];
            total+=stick[i];
        }
        if(total%4){
            cout<<"no\n";
            continue;
        }
        ave=total/4;
        sort(stick,stick+num,cmp);
        if(stick[0]>ave){
            cout<<"no\n";
            continue;
        }
        finish=false;
        dfs(0,0,0);
        if(finish)
            cout<<"yes\n";
        else
            cout<<"no\n";
    }
}