题解 P2383 【狗哥玩木棒】

fletmer · 2017-11-04 23:51:08 · 题解

#dfs+简单剪枝（ps.写代码一定要认真）
#include <cstdio>//头文件不解释
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int n,t,sum,f,cnt;//木棍数，询问次数，总长度，标记是否达成条件，当前边的长度
int len[25],che[25];//长度数组，标记是否被用过
void dfs(int e,int num,int cnt){//dfs
    if(num==4){//如果达成就标记f=1并输出
        f=1;
        cout<<"yes"<<endl;
        return;
    }
    for(int i=1;i<=n;i++){//遍历每条木棍
        if(!che[i]&&cnt+len[i]<=e){//如果未用过且不超出目标边长
            che[i]=1;//标记为用过
            if(cnt+len[i]==e) dfs(e,num+1,0);//如果当前边长正好达成，搜下一边，边长贵0
            else dfs(e,num,cnt+len[i]);//继续搜此边
            che[i]=0;//还原
            if(f==1) return;//！！！！不加这个地方会t一个点，用以更快的退出该递归
        }
    }
    return;
}
int main(){
    memset(len,0,sizeof(len));//清0
    memset(che,0,sizeof(che));
    cin>>t;//读入询问次数
    while(t--){
        cin>>n;//当前询问的木棍数
        for(int i=1;i<=n;i++){
            cin>>len[i];//读入长度
            sum+=len[i];//求木棍总长
        }
        sort(len+1,len+n+1);//排序
        if(len[n]>sum/4||sum%4!=0){//剪枝，如果最长边已超过目标边长||总长度不能被4整除就不必再搜
            cout<<"no"<<endl;
            sum=0;
            memset(len,0,sizeof(len));//清空是个好习惯
            continue;
        }
        dfs(sum/4,0,0);//目标边长，边数，当前边长度
        if(!f) cout<<"no"<<endl;//无法达成
        f=0;
        sum=0;//清空
        memset(len,0,sizeof(len));
    } 
    return 0;
}