原題アドレス

この問題はpojの少林神棍を救うのと同じ問題だ.
与えられた棒で等長の棒を寄せ集め、寄せられる棒の最小長さを求める.
直感的なバッグの中の考え方は、すべての可能な長さを列挙し、それから棒の組み合わせをテストし続け、まず棒を組み合わせに加え、それから適切でない場合はこの棒を倒し、次の棒をテストして、すべての棒を倒すまでテストします.
列挙する時、私たちは最も長い棒の長さから、棒の総長の半分まで列挙すればいいだけです.そしてこれ以上合わないと、すべての棒が1本の棒にしかならないことを意味します.
私はpojで少林神棍を救うというテーマについて詳しく説明したことがある.DFS検索問題です.ここでDFSには4つの枝切りスキームがあります.

で与えられた棒の長さは重複する可能性があり、ある棒を含む組合せ案が覆された場合、同じ長さの棒も

を試みる必要はない.

繰り返しの試験案を減らすために、例えば棒1 2 3案が不適切であることを試験し、後で棒1 3 2を試験する必要はない.では、必ず順番にテストを開始し、現在の棒が組み合わせ案に追加されたときに、まだ目標の長さを構成していない場合は、次にテストする棒は、現在の棒の次の棒からテストを開始します.

ある目標の長さの棒を集めて、その中でその最初の棒を構成して、どうしても他の棒とこの長さをまとめることができなくて、それではこの最初の棒を倒す必要はなくて、直接この目標の長さをひっくり返すことができます.

小さな棒xを加えると目標の長さになりますが、残りの棒は二度とこの長さになりません.では、この棒xをひっくり返す必要はありません.他の棒をテストして、この目標の長さを直接ひっくり返すだけでいいです.

最初は4種類の枝を切りました.しかし、まだタイムアウトで、何も言わなかった.
最後にDFS以外のmain関数に剪定があることを発見しました.私は使っていません.テストする長さは必ず全長の因数でなければ、この長さをテストする必要はありません.棒は同じ長さなので、1本1本の長さはもちろん全長の因数です.この枝が書いていないのでタイムアウトしました.

#include<iostream>
#include<cstring>
#include<functional>
#include<algorithm>
using namespace std;
bool used[64];
int len[64],n,l,last;
bool dfs(int r,int m)
{
    if(r==0&&m==0)
        return true;
    if(m==0)
        m=l;
    int start=0;
    if(m!=l)
        start=last+1;
    for(int i=0;i<n;i++)
    {
        if(!used[i]&&len[i]<=m)
        {
            if(i>0)
            {
                if(used[i-1]==false&&len[i]==len[i-1])
                    continue;
            }
            used[i]=true;
            last=i;
            if(dfs(r-1,m-len[i]))
                return true;
            else
            {
                used[i]=false;
                if(len[i]==m||m==l)
                    return false;
            }
        }
    }
    return false;
}
int main()
{
    while(cin>>n)
    {
        if(!n)
        break;
        int total=0;
        for(int i=0;i<n;i++)
        {
            cin>>len[i];
            total+=len[i];
        }
        sort(len,len+n,greater<int>());
        for(l=len[0];l<=total/2;l++)
        {
            if(total%l)// 。。
                continue;
            memset(used,false,sizeof(used));
            if(dfs(n,l))
            {
                cout<<l<<endl;
                break;
            }
        }
        if(l>total/2)
            cout<<total<<endl;
    }
    return 0;
}