Square
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5893 Accepted Submission(s): 1878
Problem 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
从第一个开始，搜索后面的看是否能正好凑够边长，小鱼的话继续深搜，大于则返回上一级，等于的话，找的的边长数++，直到边长数到达3（剩下一个不用找了，肯定也是一个边长）！！
第一次超时，每次都从第一个查找到最后一个，数据多的话超时
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
int n,a[21];
bool visit[21];
int sign;
bool DFS(int sum,int cnt,int x,int adv)
{
if(cnt == 3) //找到3个边长了，剩下一个不用再找
return true;
if(sum == adv) //组合成一个边长
{
if(DFS(0,cnt+1,x+1,adv)) //组合下一个边长
return true;
else return false;
}
else //当前边不能组成一个边长，需要向下继续组合
{
int i;
for(i = 0; i < n; ++i)
{
if(!visit[i])
{
if(sum + a[i] <= adv)
{
visit[i]=1;
if(DFS(sum+a[i],cnt,i+1,adv))
{
return true;
}
visit[i] = 0;
}
}
}
}
return false;
}
int main()
{
int t,i,len;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
len = 0;
int max=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
len += a[i];
if(max<a[i]) max = a[i];
}
if(len%4==0&& max<= len/4)
{
for(i=0;i<n;i++) visit[i]=0;
if(DFS(0,0,0,len/4)) printf("yes\n");
else printf("no\n");
}
else
{
printf("no\n");
}
}
return 0;
}
第二次改进，将每次的查找起点变为边长个数（从前往后找的话，每次都能将当前的元素个后面的组成一个边长，所以找到一个边长，则该元素肯定被用过了visit，）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,a[21];
bool visit[21];
bool DFS(int sum,int cnt,int x,int adv)
{
if(cnt == 3) //找到3个边长了，剩下一个不用再找
return true;
if(sum == adv) //组合成一个边长
{
if(DFS(0,cnt+1,cnt+1,adv)) //组合下一个边长
return true;
else return false;
}
else //当前边不能组成一个边长，需要向下继续组合
{
int i;
for(i = x; i < n; ++i)
{
if(!visit[i])
{
if(sum + a[i] <= adv) //和不能大于边长
{
visit[i]=1;
if(DFS(sum+a[i],cnt,i+1,adv))
{
return true;
}
visit[i] = 0;
}
}
}
}
return false;
}
int main()
{
int t,i,len;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
len = 0;
int max=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
len += a[i];
if(max<a[i]) max=a[i];//寻找最大值。
}
if(len%4==0&& max<=len/4) //如果和不是4的倍数，或者最大的数超过了边长
{
for(i=0;i<n;i++) visit[i]=0;//初始化visit数组
if(DFS(0,0,0,len/4)) printf("yes\n");
else printf("no\n");
}
else
{
printf("no\n");
}
}
return 0;
}