HDU_1455 && POJ_1011 Sticks (dfs)

代码+注释：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100;

int s[N];
bool used[N];

int cmp(int a, int b)
{
    return a > b;
}

bool dfs(int n, int u, int left, int len)
{
//n是木棍的总数
//u是未被拼到长度为len的原始木棍中木棍数目
//left是当前正在拼的木棍的剩余长度
//len是正在尝试的原始木棍的长度
    if(left == 0 && u == 0)    return true;
        //如果木棍都被放到原始长度的木棍中，并且剩余长度是0，则表示len是一个合法的原始长度
    if(left == 0)    left = len;    //如果当前木棍长于为0，则开始拼装一个新的原始长度木棒
    for(int i = 0; i < n; i++)
    {
        if(used[i] == true)    continue;    //已用过
        if(s[i] > left)    continue;    //如果长度比当前空余大，跳过
        used[i] = true;     //尝试将这个木棍拼入正在尝试的木棒
        if(dfs(n, u-1, left-s[i], len))    //u和left都减小，向下递归
            return true;
        used[i] = false;    //退出上次尝试的木棍，准备尝试下一个木棍
        if(s[i] == left || left == len)    break;    //如果当前尝试的是某个原始木棍中的第一个位置或者最后一个位置，并且倒是最终失败，则不必再在这个位置上尝试余下的木棍
    }
    return false;
}

int main()
{
    //freopen("data.in", "r", stdin);

    int n;
    while(scanf("%d", &n))
    {
        if(n == 0)    break;
        int i, sum = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &s[i]);
            sum += s[i];
            used[i] = false;
        }
        sort(s, s+n, cmp);    //从大到小排序
        for(i = s[0]; i <= sum; i++)
        {
            if(sum%i != 0)    continue;
            if(dfs(n, n, 0, i))
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}