北大oj1011——Sticks

Sticks

Time Limit: 1000MS Memory Limit: 10000K

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

解决了好久，差点心态崩了。
深度优先搜索。
剪枝方法：
1.由大到小进行搜索，因为大数更容易满足要求填满一根棍子，下一次搜索总数就减少了，而且大数更容易发现当前能不能行。
2.去重搜索，如果用了一根棍子发现找不到满足要求的其他棍子，那么同样长度的棍子都是不满足条件的。
3.以当前剩余长度的棍子为起始搜索，避免了中间不必要的环节。
4.减半搜索，满足条件的棍子只能是总值能整除的数，所以当搜索到总值减半的值还搜不到答案时，那么答案就是总值。

让我非常疑惑的是，我的深搜方法不知道是有什么问题，搜遍了网上提供的各项测试数据都能正常通过，但就是通不过poj，头疼，所以借鉴了一下大牛们的写法。调用函数时把要搜几根棍子传进去，一直到棍子都满足条件了再跳出函数，并且把列表回溯。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool isSuccess;
int a[71];
int gunZiLen;

void getContantGun(int lastN, int index, int useNum) {
    a[index]--;

    if (useNum == 0) {
        isSuccess = true;
    }
    if (!isSuccess) {
        lastN -= index;
        if (lastN > 0) {
            for (int i = min(lastN, index); i > 0; i--) {
                if (a[i] > 0) {
                    getContantGun(lastN, i, useNum);
                }
            }
        }
        else if (lastN == 0) {
            int maxNum = 50;
            while (a[maxNum] == 0) {
                maxNum--;
            }
            getContantGun(gunZiLen, maxNum, useNum - 1);
        }
    }
    a[index]++;
}

int main1011()
{
    int n;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        int cnt = 0;
        int maxNum = 0;
        memset(a, 0, sizeof(a));
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            cnt += x;
            a[x] ++;
            maxNum = max(maxNum, x);
        }

        isSuccess = false;
        for (int i = maxNum; i <= cnt / 2 + 1; i++) {
            if (cnt % i == 0) {
                gunZiLen = i;
                int useCnt = cnt / gunZiLen;
                getContantGun(gunZiLen, maxNum, useCnt);
                if (isSuccess) {
                    cout << gunZiLen << endl;
                    break;
                }
            }
        }
        if (!isSuccess) {
            cout << cnt << endl;
        }
    }
    return 0;
}