空间ip地址访问网站,湖南建设网塔吊证查询,文章网站后台管理系统,宁波网站建设公司名单推荐该题问给定的棍子能否组成一个正方形。首先我们要判定是否总长度是4的倍数#xff0c;然后再决定是否存在某条边大于组合边长。 搜索的过程中也是可以进行剪枝了。 首先将边排序#xff0c;我们可以假定所有的组合边由大小递减的边组成#xff0c;那么我们在搜索的时候就不用…该题问给定的棍子能否组成一个正方形。首先我们要判定是否总长度是4的倍数然后再决定是否存在某条边大于组合边长。 搜索的过程中也是可以进行剪枝了。 首先将边排序我们可以假定所有的组合边由大小递减的边组成那么我们在搜索的时候就不用再往前找边了。 其次我们可以确定任何一条边都一定在一条组合边中那么当我们以任意一条边开搜的情况下无解的话那么我们就可以直接返回no了。 最后在搜索某条边无解的情况下我们可以把相同大小的边略过因为前面相同长度的边都无法安排出一种方案在少一条相同边情况下肯定也就无法给出安排了。 代码如下 #include cstdlib
#include cstdio
#include cstring
#include algorithm
using namespace std;int N, seq[25], use[25], mode;bool dfs(int cap, int last, int num)
{if (num N) {return true;}if (cap 0) {if (dfs(mode, N1, num)) {return true;}else {return false;}}else {for (int i last-1; i 1; --i) {if (cap seq[i] !use[i]) {use[i] 1;if (dfs(cap-seq[i], i, num 1)) {return true;}else {use[i] 0;if (i N) {return false;}while (seq[i-1] seq[i]) --i;} }}}return false;
}int main()
{int T, sum, Max;scanf(%d, T);while (T--) {sum 0, Max -1;memset(use, 0, sizeof (use));scanf(%d, N);for (int i 1; i N; i) {scanf(%d, seq[i]);Max max(Max, seq[i]);sum seq[i];}if (sum % 4 ! 0 || Max sum / 4) {puts(no);continue;}sort(seq1, seqN1);mode sum / 4; // 每一边的大小printf(dfs(mode, N1, 0) ? yes\n : no\n);}return 0;
} 转载于:https://www.cnblogs.com/Lyush/archive/2012/07/25/2607549.html
