题意:
给你n个小棒碎片,要求还原原棒长,求最短原棒长
要点:
经典搜索题,有很多剪枝,很早之前就想做一下,现在终于有水平可以做了,感觉水平还是有进步的,原来根本看不懂,现在好歹看的懂了,主要是各种剪枝实在是比较难想到。
从最大的一个碎片开始到碎片总和,一个个DFS是否为原棒长
剪枝:
1.原棒长必须是总数的因数
2.每次一开始从最大的碎片开始遍历,如果每次一开始的无法搜索成功直接剪掉,比如5,4,2,2要找6,用5遍历找不到,那么后面就不用算了,但要注意有可能一开始可以,后面出现失败的情况,比如5,1,5,2,3找6,一开始5+1找到了,但后面重新搜索时找不到,它剪枝剪掉的是每次重新寻找找不到的情况,所以要注意某些地方的位置不能颠倒,(这部分与剪枝4有部分重复,但最一开始的已经剪枝足够多,所以无法替代)
3.相同的不用再算直接跳掉,比如5,5,4,4,第一个5搜索不成功就不需要算第二个5了,同理5+4失败就不需要算第二个4
4.如果已经拼出一个,下一个如果拼不出来,直接剪掉,比如5,1,3,1,4,第一次5+1=6满足了,但第二次搜索是搜不出6的,那么后面不用算了,因为肯定都拼不出了
代码如下;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[100];
bool vis[100];//标记数组
int num, n, len;int cmp(const void *a, const void *b)
{return *(int*)b - *(int*)a;//从大到小排列
}bool dfs(int x,int pos,int l)
{if (x == num-1) //最后一个一定满足不用考虑return true;bool sign = (l == 0 ? true : false);int i;for (i = pos + 1; i < n; i++) //注意这里从pos+1开始{if (!vis[i]){if (l + a[i] == len){vis[i] = true;if (dfs(x + 1, -1, 0))return true;vis[i] = false;return false;//已经拼出一个,后面如果失败就全失败直接剪掉}else if (l + a[i] < len){vis[i] = true;if (dfs(x, i, l + a[i])) //这里从i开始,因为前面已经-1了return true;vis[i] = false;//注意这个要放在这个位置,因为有可能第一次成功了,第二次从头开始失败 if (sign)return false; //判断每次第一个能否成功,失败后面就不用算了while (a[i] == a[i + 1])//如果失败就跳过后面相同的i++; //注意因为这里所以上面从pos+1开始}}}return false;
}int main()
{while (scanf("%d", &n) != EOF, n){int sum = 0;for (int i = 0; i < n; i++){scanf("%d", &a[i]);sum += a[i];}qsort(a, n, sizeof(a[0]), cmp);for (len = a[0]; len <= sum; len++){if (sum%len == 0) //len肯定是sum的因数{num = sum / len; //有num根原始棒子memset(vis, false, sizeof(vis));//每次都要先把标记数组清零if (dfs(0, -1, 0)){printf("%d\n", len);break;//达到就直接跳出,保证最小}}}}return 0;
}