Square
Time Limit:3000MSMemory Limit:65536K
Total Submissions:21821Accepted:7624
Description
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
Input
The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick – an integer between 1 and 10,000.
Output
For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".
Sample Input
34 1 1 1 15 10 20 30 40 508 1 7 2 6 4 4 3 5
Sample Output
yesnoyes
这个题和POJ1011觉得真的是两道特别棒的题目，，仔细琢磨很有味道。这个题一开始输出大写的YES和NO导致WA了一次。。。
题意是给你M根木棒，接下来给你每根木棒的长度，问这些木棒是否能够构成一个正方形。
具体理解见代码：
#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <string>#include <cstring>#pragma warning(disable:4996)using namespace std;int num_s,flag,sum;int stick[25];bool visit[25];bool dfs(int num,int length,int stick_st,int * stick,bool *visit){if(num==4)return true;int i;for(i=stick_st;i<=num_s;i++){if(visit[i])continue;visit[i]=true;if(length+stick[i]<(sum/4)){if(dfs(num,length+stick[i],i+1,stick,visit)){return true;}}else if(length+stick[i]==(sum/4)){if(dfs(num+1,0,1,stick,visit)){return true;}}visit[i]=false;}return false;}bool cmp(const int a,const int b){return a>b;}int main(){int Test,i;cin>>Test;while(Test–){cin>>num_s;sum=0;flag=0;for(i=1;i<=num_s;i++){cin>>stick[i];visit[i]=false;sum += stick[i];}if(num_s<4||sum%4)//剪枝1：如果木棒数量小于4，cut。//剪枝2：如果sum的和不能整除4，cut。{cout<<"no"<<endl;}else{sort(stick+1,stick+1+num_s,cmp);if(stick[1]>sum/4)//剪枝3：如果最大的一根木棒大于了sum/4,cut。cout<<"no"<<endl;else{if(dfs(1,0,1,stick,visit))//第一个数代表当前要完成的第几根木棒//第二个数代表当前已经完成的长度//第三个数代表从第几个木棒开始查找的{cout<<"yes"<<endl;}else{cout<<"no"<<endl;}}}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
德高培身，财多伤身。
