zoj1909(0.0).cpp

这是浙大acm,北大acm上,还有地大acm上的题解,全部是关于搜索算法的,题目文件名上有

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int side[21], m ,ave;
int mark[21], flag;

int cmp(const void *a ,const void *b){
    return (*(int *)b - *(int *)a);
}
  
void find(int st, int len, int cnt, int index){
    int i;
    if(cnt == 4 && index == m){
        flag = 1;
        return ;
        }
    if(len == 0){
        for(i = 0; i < m ; i++)
            if(!mark[i]) break;
        mark[i] = 1;
        if(len + side[i] == ave)
            find(0, 0, cnt+1, index + 1);
        else find(0, len + side[i], cnt, index + 1);
        mark[i] = 0;
        return ;
        }
    for(i = st; i < m; i++){
        if(!mark[i] && len + side[i] <= ave){
            mark[i] = 1;
            if(len + side[i] == ave)
                find(0, 0, cnt + 1, index + 1);
            else find(i + 1, len + side[i], cnt, index + 1);
            mark[i] = 0;
            if(flag) return ;
            }
        }
}

int main(){
	int tcase, i, sum;
	scanf("%d", &tcase);
	while(tcase--){
		scanf("%d", &m);
		for(sum = 0, i = 0; i < m; i++){
			scanf("%d", &side[i]);
			sum += side[i];
		}
		if(sum % 4 ){
			printf("no\n");
			continue;
		}
		qsort(side, m, sizeof(int), cmp);
		ave = sum / 4;
		if(side[0] > ave){
			printf("no\n");
			continue;
		}
		flag = 0;
		memset(mark, 0, sizeof(mark));
		find(0, 0, 0, 0);
		if(flag) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

/*
leemars
次这道题是要求判断是否能将所给的M条木棍拼接成一个正方形。
由于边长最大可达10000，用动态规划显然不切实际，所以我们考虑使用搜索。
在搜索之前，我们应先判断问题是否一定无解，以避免不必要的搜索。
先计算出M条木棍的总长sum，如果sum不是4的倍数，显然这M条木棍不可能组成正方形。
再计算出正方形每一边的长度max = sum / 4，如果M条木棍中有长度大于max的，
则这M条木棍也不可能组成正方形。对于这两种情况，可以马上输出"no"。
设square[i] = max表示正方形第i条边剩余的长度。
对于这个问题，搜索的方式有很多种：
(1)以数为阶段进行搜索，每次考虑将一条木棍放在一条边上。
(2)以正方形的边为阶段进行搜索，每次考虑往某一条边上放木棍。
显然，第二种搜索方式可以更好的利用可行性剪枝及早回溯，比第一种搜索方式高效得多。
因此，我们的搜索算法就定下来了：每次对一条边进行搜索，
从没有用过的木棍中选一条放在上面，如果square[i] = 0则搜索下一条边，
否则继续搜索当前边。一但所有边都可以成功安排，
输出"yes"，否则最后输出"no"。
我们还可以进行一些优化：
(1)直觉上先安排长度大的木棍可以更快的找到解或是回溯，
因此搜索前我们就将木棍按长度从大到小排序。
事实证明这一优化是相当有效的，先安排小的程序耗时0.11s，先安排大的程序仅耗时0.05s。
(2)在搜索过程中还应该避免一些重复的枚举，即对某一条边进行搜索时，
保持枚举变量单调递增。除了这样，搜索各条边时，还可以保持起点的枚举变量单调递增。
通过这样的有序化，可以减少不必要的搜索，提高出解的速度。
(3)对于第一条边，我们可以直接将一根木棍指定上去：
因为这条边若不包含这条木棍，由于枚举变量的有序化，
这根木棍以后就不可能再被使用了，与题意不符，
所以这根木棍一定在这条边上。通过这样的指定，我们就减少了搜索量（主要是对于无解的情况）。
这个优化使程序的时间从0.05s减少到了0.02s，相当厉害！
(4)除了第一条边可以直接将一根木棍指定上去，我们稍加思考后还会发现，
在对每一条边进行搜索时，都可以将第一根未使用的木棍指定上去，理由同上。
这个进一步的优化，使程序的时间从0.02s降到了0.00s，完美解决问题！
(5)我们还可以把最后一条边的搜索去掉，因为搜完前三条边后，剩下的木棍必然是第四条边上的。
只要将剩下的木棍的长度加起来进行判断即可。不过这一优化对我程序的时间已经产生不了影响……
(6)这道题能不能用分类的方法剪枝呢？应该是可以的，这样就减少了一些重复搜索的组合。
但是这道题的限制条件（正方形等）太强了，以至于这个剪枝发挥的作用相当小。
*/