#include <iostream>
#include <fstream>

using namespace std;
#define MAX 64
#define VERYLARGE 1000000

int stick[MAX];
int diff[MAX];      //  在第几中被占用了
int mark[MAX];      //  在第几中被占用了
int nCount, nSum, nResult = 0;

int IsFinished(int nMark)
{
    for (int i = 0; i < nCount; i ++)
    {
        if (mark[i] > nMark) return 0;
    }
    return 1;
}

void dfs(int nGoal, int nTemp, int nBegin, int nMark) // 计算函数
{       // 从stick中由nBegin开始找出小于 nGoal - nTemp的数
        // 现在已经的和为nTemp,nMark该组起始数的索引为（用以区分）
    // 全搜索、遍历所有可能
    int i;
    for (i = nBegin; i < nCount; i ++)  
    {
        if (!(mark[i] > nMark && !nResult && nTemp + stick[i] <= nGoal))
            continue;
        mark[i] = nMark;
        if (stick[i] + nTemp == nGoal)   // 如果相等
        {
            if (IsFinished(nMark)) 
            {
                nResult = nGoal;  return;
            }//
            dfs(nGoal, 0, nMark + 1, nMark + 1);
        }
        else
        {
            dfs(nGoal, nTemp + stick[i], i + 1, nMark);
        }
        if (!nResult)
            mark[i] = VERYLARGE;
        while (!nResult && i < nCount && stick[i] == stick[i + 1]) i ++; // 剪枝
    }   // for
}

int calculate()
{
    int i;
    for (i = stick[0]; i < nSum; i ++)
    {
        if (nResult) break;
        if (!(nSum % i)) dfs(i, 0, 0, 0);
    }
    if (!nResult)
        nResult = nSum;
    return nResult;
}

int compare(const void* a,const void* b)
{
    return *(int*)b - *(int*)a ;
}

int main()
{
    cin >> nCount;
    while (nCount)
    {
        if (nCount < 0 || nCount > 64) 
            continue;
        memset((void*)stick, 0, sizeof(int) * MAX); //清零
        int i;
        nSum = 0;
        for (i = 0; i < nCount; i ++)
        {
            cin >> stick[i];
            if(stick[i] > 50 || stick[i] <= 0)
                stick[i] = 0;
            mark[i] = VERYLARGE;
            nSum += stick[i];
        }   //  for

        nResult = 0;
        //  开始计算
        qsort(stick, nCount, sizeof(int), compare);
        int j = 0;
        for (i = 0; i < nCount - 1; i ++)
        {
            diff[i] = 0;
            if (stick[i] != stick[i + 1])
                diff[i] = i + 1;
        }
        
        calculate();
        cout << nResult << endl;
        cin >> nCount;
    };  //  while

    return 0;
}

• 记得按LRJ黑书上的说法，如果搜索顺序和剪枝OK的话，满足题意的任何数据运算都不会超过100ms (2614) ACM06021fly 2006-12-11 21:11:11
  • Re:记得按LRJ黑书上的说法，如果搜索顺序和剪枝OK的话，满足题意的任何数据运算都不会超过100ms (23) piratelzs 2006-12-30 15:11:35
• 经过测试，这组数据绝对是过不了！！　＞３０秒后才出结果． (503) winboycool 2007-04-22 21:40:01
  • 这组数据我0MS 可以解出 但提交确实TLE (22) entrails 2007-08-04 02:30:38
    • Re:这组数据我0MS 可以解出 但提交确实TLE (34) stzengql 2009-07-29 20:06:54
  • Re:经过测试，这组数据绝对是过不了！！　＞３０秒后才出结果． (571) LittleKid 2007-08-10 19:22:27