|
Language:
Square
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 3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5 Sample Output yes no yes
|
这个题是一个DFS回溯的问题。我们可以求出来变长，我们只需要用已有的枝条凑出三个边长的长度，我们就可以返回成功。
我们还需要考虑到的是剪枝的简化运算。以下几个地方可以考虑去剪枝：1.首先所有木条的长度总和必须是4的倍数。2.满足1的前提下，我们可以计算正方形边长。如果最长的木条必须比边长要短。
为了简化运算，我们考虑将木条的长度排序，因为木条越长它的灵活性越差，我们需要尽早将长的木条凑进去。
贴上代码：
/*************************************************************************
> File Name: Square.cpp
> Author: Zhanghaoran0
> Mail: chiluamnxi@gmail.com
> Created Time: 2015年07月28日 星期二 16时59分48秒
************************************************************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int T;
int n;
int a[30];
bool flag[30];
int sum = 0;
bool dfs(int num, int pos, int len){
if(num == 3)
return true;
int i;
for(i = pos; i >= 0; i --){
if(!flag[i]){
flag[i] = true;
if(len + a[i] < sum){
if(dfs(num, i - 1, len + a[i]))
return true;
}
else if(len + a[i] == sum)
if(dfs(num + 1, n - 1, 0))
return true;
flag[i] = false;
}
}
return false;
}
int main(void){
cin >> T;
while(T --){
cin >> n;
bool temp = true;
sum = 0;
memset(flag, 0 ,sizeof(flag));
if(n < 4){
cout << "no"<< endl;
continue;
}
for(int i = 0; i < n; i ++){
cin >> a[i];
sum += a[i];
}
if(sum % 4 != 0){
cout << "no"<< endl;
continue;
}
sum /= 4;
sort(a, a + n);
if(a[n - 1] > sum){
cout << "no" << endl;
continue;
}
if(dfs(0, n - 1, 0))
cout << "yes" << endl;
else
cout <<"no"<< endl;
}
}