当前位置: 代码迷 >> 综合 >> POJ2362 DFS+剪枝
  详细解决方案

POJ2362 DFS+剪枝

热度:25   发布时间:2024-01-16 14:03:56.0

题意:

有一组小棒,这些小棒全用上看能不能拼成一个正方形,可以多个小棒拼成一条边

要点:

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;
}



  相关解决方案