题解 P2383 【狗哥玩木棒】

DDOSvoid · 2017-08-13 20:59:40 · 题解

明显DFS

提供一种特殊的dfs思路

既然要拼成一个正方形，那么所有木棍的长度总和一定能被4整除，如果不能，直接输出“no”

注释和思路都在代码里

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 21
using namespace std;
int w[5],a[maxn],t,n,sum;
bool f;
void dfs(int q){
    if(f)return ;
    if(q==n+1){//如果能搜到这最后一层，则代表可以组成正方形 
        f=1;
        return ;
    }
    for(int i=1;i<=4;i++)
        if(w[i]>=a[q]){
            w[i]-=a[q];
            dfs(q+1);
            w[i]+=a[q];
        }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        sum=0;f=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),sum+=a[i];
        if(sum%4){
            cout<<"no"<<endl;
            continue;
        }
        for(int i=1;i<=4;i++)
            w[i]=sum/4;//w数组代表正方形的4条边 
        sort(a+1,a+n+1,greater<int>());//一定要从大到小排序，先放长度大的木棍，一种优化思想，排序0ms，不排序的40ms 
        dfs(1);
        if(f)cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
}