Square HDU 1518 搜索
题意
给你一定若干个木棒，让你使用它们组成一个四边形，要求这些木棒必须全部使用。
解题思路
木棒有多种组合方式，使用搜索来进行寻找，这里需要进行优化，不然复杂度非常高。
因为M最大为20，所以，如果用DFS还是可以接受的。
由所有火柴棒的长度和，我们可以求出要组成正方形的边长。我们设边长为len。在搜索前，首先可以把边长为分数的，也就是火柴棒的长度和不能被4整除的，排除掉。
问题可以转化为从M个数中挑出4组和为len的数。
首先，从M个数中搜索出和为len的数。如果能搜到，则接着从剩余的数中，进行同样的搜索，依此类推，一共进行4段这样的搜索。
如果某一段搜索失败，则回溯到上一段搜索。
如果一直回溯到第一段的搜索，仍未能找到解，则说明无解。
搜索过程
将长度按从大到小排序。
对应正方形的4条边，进行4段同样的搜索。而且这4段搜索也是递归式的，就是说，当第一段边搜索到后，便递归进行下一段的搜索。由此可见，搜索过程中要用到的信息包括：当前是第几段；当前段还剩余的长度；搜索的起始位置。
每段搜索的过程是相同的：因为到最后，所有的火柴棒都是会被用到的，所以，每当开始一个新段的搜索时，总是把剩余的第一个数放入，在这段的搜索过程中，它始终是放入状态。然后进入堆栈的下一层，试着放入下一个剩余的数，如果放入这个数后递归到下面未回溯回来，则说明已经找到最后答案，程序结束。如果得到回溯，那么把该数取出，同理再试着放入排在它后面的数。
搜索的起始位置
起始位置就是，在每次进入递归函数的时候，应该从哪个位置的数开始试着放入；如果这次递归要放入的是一个段的第一个数，这个数肯定是剩余的第一个数，而且这个数是不会被取出的，也就是说，这一层的可选状态只有一个，如果放入这个数之后，后面发现无法搜索到一个完整的边，那么说明剩余的数到达最终的目标，必须回溯到上一个段。
如果这次递归要放入不是一个段的第一个数，那么它的起始位置肯定是在它上一层递归放入的数的后面，但是它前面可能还存在没有被放入的数，这些数就不用再试了吗？
因为是对同一个段的搜索，所以，组成这个段的数被放入的顺序是没有关系的。所以，如果一个数作为一个段的第一个数放入不合适，那么它作为第二个数或第三个数放入肯定也是不合适的。
代码实现
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e4+7;
int a[maxn], vis[maxn], sum;
int m, len;
bool dfs(int duan, int begin, int left)//记录当前的段数，数组的位置，当前段还需要多长的木棍
{
if(left==0)
{
if(duan==3) return 1;
int i;
for( i=1; i<=m && vis[i]!=0; i++);
vis[i]=1;
if(dfs(duan+1, i, len-a[i])) return 1;
vis[i]=0;
return 0;
}
for(int i=begin; i<=m; i++)
{
if(vis[i]==1 || a[i] > left) continue;
if(i>1 && vis[i-1]==0 && a[i-1]==a[i]) continue;
vis[i]=1;
if(dfs(duan, i, left-a[i])) return 1;
vis[i]=0;
}
return 0;
}
bool cmp(int a, int b)
{
return a>b;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d", &m);
sum=0;
for(int i=1; i<=m; i++)
{
scanf("%d", &a[i]);
sum+=a[i];
vis[i]=0;
}
if(sum%4!=0)
{
printf("no
");
continue;
}
sort(a+1, a+1+m, cmp);
len=sum/4;
if(a[1] > len)
{
printf("no
");
continue;
}
vis[1]=1;
if( dfs(1, 1, len-a[1]) )
printf("yes
");
else printf("no
");
}
return 0;
}