描述
给你一些木棍，让你用这些木棍在地上摆出一个正方形的轮廓。如果能摆成，输出"yes",否则输出"no"。
输入
第一行有一个正整数t表示数据组数 每组数据占一行，一行中第一个数n（4<=n<=20）表示木棍的根数，接下来的n个数字表示每个木棍的长度。
输出
如果能摆成正方形，输出"yes",否则输出"no"。
样例输入
3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5样例输出
yes no yes题目来源
jhf
题目知识点：dfs
AC代码：
#include<iostream> #include<algorithm> using namespace std; const int MAXN=21; int a[MAXN]; bool vis[MAXN]; int N,ave,curlen,sum; bool cmp(const int &a, const int &b){ return a>b; } bool dfs(int step,int num){ if(num>3) return true; if(step>=N) return false; if(!vis[step]&&(a[step]+curlen)<=ave*num){ vis[step]=true; curlen+=a[step]; if(curlen==ave*num){ if(dfs(0,num+1)) return true; } else if(dfs(step+1,num)) return true; vis[step]=false; curlen-=a[step]; } return dfs(step+1,num); } bool judge(){ if(N<4||sum%4!=0) return false; ave=sum/4; for(int i=0;i<N;i++) if(a[i]>ave) return false; sort(a,a+N,cmp); memset(vis,false,sizeof(vis)); curlen=0; return dfs(0,1); } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&N); sum=0; for(int i=0;i<N;i++){ scanf("%d",&a[i]); sum+=a[i]; } if(judge()) cout<<"yes\n"; else cout<<"no\n"; } system("pause"); return 0; }
