题目：http://poj.org/problem?id=1011
这题我莫名其妙的0ms过的，本来是用discuss那个测试数据，跑半天都没有结果，然后看到有一个人思路跟我很像，就把他的用来试试那组坑人的数据，结果也是跑半天都没有结果，我把他的提上去居然A了，32ms，然后就提提我的，居然0ms。好吧，还是poj的数据太弱
题意就是有一堆木棍，然后要把它们拼凑成长度一样的。并要求这个长度是满足条件最小的
思路，对满足能跟整除所有木棍之和的长度进行枚举，然后进行深搜，dfs(int len, int num, int cur_len);//这里三个参数的意思是len是搜索的长度，num是已经搜索的木棍的个数，cur_len当前正在拼凑的木棍的长度。然后对于没有使用过的木棍i，如果cur_len + stick[i] <= len 就把该木棍标记为已经选上去，重点不是搜索啦，而是剪枝
代码：
#include<cstdio> #include<algorithm> using namespace std; int N, sum; int stick[64]; bool cmp(int a, int b) {//对stick进行升序排列，这样可以减少递归次数 return a > b; } bool dfs(int len, int num, int cur_len) { if(num == N) {//已经搜索到第N根木棍直接返回，不需要管这时的cur_len是否跟len相等。因为已经有前提sum%len == 0，前N-1 根找出来了，剩下的肯定能找出来，所以直接返回就ok return true; } if(cur_len == len) {//正在拼凑的木棍昌墩为len了，就把它初始化为0，表示已经拼凑完一根木棍 cur_len = 0; } for(int i = 0; i < N; ++ i) { if(stick[i] != 0) {//这里偷了一下懒，懒得用visited，直接stick[i] == 0表示这根木棍被用过了 if(cur_len + stick[i] <= len) { int temp = stick[i];//暂时记录，后面回溯时用到 stick[i] = 0; if(dfs(len, num + 1, cur_len + temp)) {//搜索成功就直接返回 return true; } stick[i] = temp;//回溯 if(cur_len + temp == len || cur_len == 0) {//剪枝，是表示如果当前这根木棍正好可以拼凑成一个len长度，或者正在进行一根新的木棍的拼凑，但搜索还是失败了，说明这次搜索的结果就是失败的，所以直接退出 break; } while(i < N - 1 && stick[i] == stick[i + 1]) {//这根不行的话，跟它长度一样的也就不行 i++; } } } } return false; } int main() { freopen("poj1011.txt", "r", stdin); while(scanf("%d", &N), N) { sum = 0; for(int i = 0; i < N; ++ i) { scanf("%d", &stick[i]); sum += stick[i]; } sort(stick, stick + N, cmp); for(int len = stick[0]; len <= sum; ++ len) { if(sum % len == 0) { bool flag = dfs(len, 0, 0); if(flag) { printf("%d\n", len); break; } } } } } |