题目背景
狗哥又趁着语文课干些无聊的事了...
题目描述
现给出一些木棒长度，那么狗哥能否用给出的木棒（木棒全用完）组成一个正方形呢？
输入输出格式
输入格式：
输入文件中的第一行是一个整数n表示测试的组数，接下来n行表示每组的测试数据。 每行的第一个数为m(4<=m<=20),接下来m个数ai(1<=ai<=1000)表示木棒的长度。
输出格式：
对于每组测试数据，如果可以组成正方形输出“yes”，否则输出“no”。
输入输出样例
输入样例#1：
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
输出样例#1：
yes
no
yes
说明
狗哥快抓狂了
题目大意：t组测试 n个木棒 是否能拼成一个正方形
题解：
dfs.
a、因为木棒都要用完，所以木棒的长度和%4！=0 直接输出No
b、最长的木棒大于求出的正方形的边 输出no (sum/4)
代码：
洛谷上面一个代码很好...我加了b的判断
我写的略丑..=L=
搜索用完n个木棒。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int t,n,sum,flag,maxx,w[],a[];
void dfs(int q){
if(q==n+){flag=;return;}
if(flag)return;
for(int i=;i<=;i++){
if(w[i]>=a[q]){
w[i]-=a[q];
dfs(q+);
w[i]+=a[q];
}
}
}
int main(){
scanf("%d",&t);
while(t--){
sum=;flag=;maxx=-0x7ffffff;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];maxx=max(maxx,a[i]);
}
if(sum%){
printf("no\n");
continue;
}
if(maxx>sum/){
printf("no\n");
continue;
}
for(int i=;i<=;i++)
w[i]=sum/;
sort(a+,a+n+,greater<int>());
dfs();
if(flag)printf("yes\n");
else printf("no\n");
}
return ;
}
换个风格
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,a[],flag,sum,maxx,vis[];
void dfs(int l,int v){
if(v==&&l==sum){flag=;return;}
if(flag)return;
if(l==sum)l=,v+=;
for(int i=;i<=n;i++){
if(!vis[i]&&l+a[i]<=sum){
vis[i]=;
dfs(l+a[i],v);
vis[i]=;
}
}
}
int main(){
scanf("%d",&t);
while(t--){
flag=;sum=;maxx=-0x7ffff;
scanf("%d",&n);
maxx=-0x7ffffff;sum=;
for(int i=;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];maxx=max(maxx,a[i]);}
if(sum%||maxx>sum/){printf("no\n");continue;}
sum/=;
sort(a+,a+n+,greater<int>());
dfs(,);
if(flag)printf("yes\n");
else printf("no\n");
}
return ;
}