题意:
有一组小棒,这些小棒全用上看能不能拼成一个正方形,可以多个小棒拼成一条边
要点:
DFS+剪枝,这题才是真正的搜索题,做的我心潮澎湃,相比前面那一题根本就不能算是搜索。
DFS:
先排序,从最大的小棒开始搜索(最大的小棒需要的最少),定义一个数组,使用了这根小棒就改为,就不能再使用,只能使用值为的,用len记录现在拼成的长度,x记录已经完成的多少边
剪枝:
1.小棒加起来总数/4如果不为整数舍去
2.每边长度都要大于等于最大边
3.输入小棒数n<4舍去
4.满足三条边即可,剩下的第四条边肯定满足
代码如下:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int a[25], vis[25]; //用来记录有没有用过
int n,l;int cmp(const void *a, const void *b)
{return *(int*)a - *(int*)b;
}int dfs(int x, int pos, int len)
{ //x代表已经找到的边数,pos为当前位置,len代表已经拼成的长度int i;if (x == 3) //只要满足3条边剩下一条一定满足return 1;for (i = pos; i >= 0; i--){if (!vis[i]){vis[i] = 1; //说明这一条已经用了if (len + a[i] < l){ //如果拼起来还是小于l就再从前面找if (dfs(x, i - 1, len + a[i])) return 1;}else if (len + a[i] == l){ //如果拼起来等于l,x+1从新开始搜索if (dfs(x + 1, n - 1, 0))return 1;}//注意这里不能加else,可能有些精度的问题vis[i] = 0; //加起来大于边这条用不了}}return 0;
}int main()
{int i,sum,t;scanf("%d", &t); while (t--){sum = 0;scanf("%d", &n);for (i = 0; i < n; i++){scanf("%d", &a[i]);sum += a[i];}l = sum / 4;qsort(a, n, sizeof(a[0]), cmp);memset(vis, 0, sizeof(vis));if (l * 4 != sum || n < 4 || l < a[n - 1])//剪枝{printf("no\n");continue;} if (dfs(0, n-1, 0))printf("yes\n");elseprintf("no\n");}return 0;
}