HDU1455 Sticks dfs+剪枝

该题与上题相比增加了多种分法，而不只是四条边，问题是最多能够分成多少条边。

上题代码其实错了（已改），但是也过了，这题改的还纠结。

代码如下：

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N, seq[100], mode, use[100], flag;

void dfs(int cap, int last, int num)
{
    if (num == N) {
        flag = 1;
        return;
    }
    if (flag) {
        return;
    }
    if (cap == 0) {
        dfs(mode, N, num);
    }
    else {
        for (int i = last; i >= 1; --i) {
            if (cap >= seq[i] && !use[i]) {
                use[i] = 1;
                dfs(cap-seq[i], i - 1, num + 1);
                use[i] = 0;
                if (last == N || flag) {
                    // 如果连第一条边都无法选择的话
                    return;
                }
                while (seq[i-1] == seq[i]) --i;
            }
        }
    }
}

int main()
{
    int sum, Max;
    while (scanf("%d", &N), N) {
        sum = 0, Max = -1;
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &seq[i]);
            Max = max(Max, seq[i]);
            sum += seq[i];
        }
        sort(seq+1, seq+N+1); 
        for (int i = N; i >= 1; --i) {
            if (sum % i == 0) {
                memset(use, 0, sizeof (use));
                flag = 0;
                mode = sum / i; 
                dfs(mode, N, 0);
                if (flag) {
                    printf("%d\n", mode);
                    break;
                }
            }
        }
    }
    return 0;
}