这道题算法题：sticks，我一直是答案错误50%，请问是为什么啊？？？

Question

题目：

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

Hint

题意

给定n根木棒，要求将它们拼成若干根等长的木棒，问拼成的木棒最短长度。

题解：

dfs+剪枝。

将木棒从长到短排序，枚举能拼成的长度搜索，枚举范围是最长木棒的长度到所有木棒总长度中能被总长度整除的部分。

搜索：从最长的木棒开始搜，每搜到一根组合好的木棒变换搜索状态，继续从最长的开始搜，直到用完所有木棒。

剪枝：

1.当某根木棒无法完成组合，则无解，直接结束此次搜索，回溯到上一步；

2.当某个长度的木棒不能再此次搜索中使用，则跳过所有该长度木棒的搜索。

我的代码：

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int visit[70] = { 0 }, sticks[70];
int sum=0,n=0,len;
bool compare(int a, int b)
{
    return a>b;
}
int main()
{
    bool dfs(int start,int snowlen,int nowlen);
    while (cin >> n)
    {
        if (n == 0)
            break;
        for (int i = 0; i < n; i++)
        {
            cin >> sticks[i];
            sum += sticks[i];
        }
        sort(sticks, sticks + n, compare);
        for (len = sticks[0]; len <= sum; len++)
        {
            if (sum%len == 0)
            {
                if (dfs(0, 0, 0))
                {
                    cout << len << endl;
                    break;
                }
            }
            memset(visit, 0, sizeof(visit));
        }
        memset(sticks, 0, sizeof(sticks));
        sum = 0;
    }
    return 0;
}

bool dfs(int start,int snowlen, int nslen)
{
    for (int i = start; i < n; i++)
    {
        if (snowlen + sticks[i] <= len && visit[i] == 0)
        {
            visit[i] = 1;
            int x,ss;
            x = i;
            ss = snowlen + sticks[i];
            nslen += sticks[i];
            if (snowlen + sticks[i] == len)
            {
                x = 0;
                ss = 0;
            }
            if (nslen == sum)
                return true;
            if (dfs(x, ss, nslen) == true)
            {
                return true;
            }
            visit[i] = 0;
            if (snowlen + sticks[i] == len || snowlen == 0)
                return false;
            while (sticks[i + 1] == sticks[i])
                ++i;
        }
    }
    return false;
}

Answer 1

MXGNWDJWMFVRNGKTZKTNFRMIXXTKQVBLYYKUEUGDTBRAYBIERBEAXDGRTTZIKHARKAGTPLVUHRXUKLBFFHYNUPFFZFYECLSVVWMMOUUHKKWZPSKJPWZCCAZWPJMGGWSFZCCVKGVPPSSEOLESUKROOLOKERJJFLRFFVYYLXQJGJMYISVRIHOOHHXNJJJCVHOUGWKGTMOXGKUKTMJTTJWSIYBRXAKCBXQQZFVEYYTOAJNQCMJISSLUUIEKAOHNNAZIPIEHDDMWOKJATUKHKNNGAFOHMPGCCMEDPGHBXDKNDYQJPLFENXXXRRJNPZUAAAKIUQXHNODDMWJCWJCZIBRYOSBDAJTQDWMIHQTZWNPDQTJEXGMFUHUKRAIBQWZOEBXXJIOXXGLBDDNNBXXQTCOBNUEAQSAAMSSIZLXGGGPFVYLKKAGOSPOELHBEKTRQYFYRRHALKDUNNDUKKPPMTJMMPKDNNQDCZPPEZJZMYUAARAIIVOYAJDWZEGJMGCATJBUOEUNHXFCJTFOYMADKRSRVYWGZCFZSYUHGDOKASSEXRHAGVSCCVZWBYHIEYGPVIVUAXFPMTCCSRQYHRARKUEQLEKXGGJISCORKTDXGTCBROHNJBEOHTGJSVIUOOORGCILTCSVLIQZCYTOEOEHWTPFPMJYPFPFORSVWZIMBRTJSCEEYHQGWMPLVLSVKUWMWSCYBJXTVFIXGJMVLNDKPMPYVFOZCKMVXUQZCYLAWZVFBXTJYQZPFPSHRADTIENDGCLGWFVPSBXAWZVYHCURTPSIKBKHVAIDIQGDSPFVXNWSIYFPRBXHPYBRBRUWMPKTWZORVEBKNKGCLOETDMIYSODMCSOLHRMLSOXALUXTDSWACMPKHXZPS