uva307 dfs

블로그를 코드를 기록하는 곳으로 삼아라.이 문제는 생각해 보니 정말 괜찮은데 거슬러 올라가는 법에 대한 이해를 높일 수 있다.제목은 이해하기 어렵지 않다. 잘라낸 작은 나무 막대기 한 무더기를 모아서 합친 작은 나무 막대기의 최소 길이를 찾아라. 가장 중요한 것은 이 작은 나무 막대기의 합친 길이가 똑같다는 것이다.
내가 시작한 사고방식은 몇 개의 작은 나무 방망이를 일일이 열거한 후에 전체적인 근수를 나누면 작은 나무 방망이의 길이를 얻을 수 있다. 그리고 하나하나 판단한 결과 아무리 써도 쓸 줄 모른다고 쓰여 있어서 인터넷에서 대신들의 코드를 참고했다.사고방식: 직접 매거 길이를 구한 다음에 귀속을 통해 근수를 구한 다음에 곱한 후에 총 길이와 같을 수 있는지 판단하면 된다. 여기서 주의해야 할 것은 매거의 길이는 반드시 나무 막대기의 최대 길이보다 크고 총 길이보다 작아야 한다는 것이다.인터넷의 대신들은 모두 가지치기를 사용한 것 같지만, 나는 가지치기를 하든 안 하든 똑같다고 생각한다(자신이 너무 약해서 구별이 안 될 수도 있다) 그래서 가지치기를 하지 않았다.더 이상 말하지 말고 코드를 입력하십시오.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxed=100+10;
int panDuan[maxed],n,muBang[maxed],changDu,zong;
int main()
{
    bool slove(int,int,int);
    bool cmp(int,int);
    while(scanf("%d",&n)!=EOF&&n){
        //memset(panDuan,0,sizeof(panDuan));
        memset(muBang,0,sizeof(muBang));
        int t;
        zong=0;
        for(int i=0;i<n;i++){
            scanf("%d",&t);
            muBang[i]=t;
            zong+=t;
        }
        sort(muBang,muBang+n,cmp);//         ，            ，       。
        for(changDu=muBang[0];changDu<=zong;changDu++)
            if(!(zong%changDu)){
                //cout<<2<<endl;
                memset(panDuan,0,sizeof(panDuan));
                if(slove(0,0,0))
                    break;
            }
        printf("%d
",changDu);
    }
    return 0;
}
bool cmp(int x,int y)
{
    return x>y;
}
bool slove(int now,int geShu,int cur)//now    ，geShu       ，cur        （        ，      0           ）
{
    //cout<<1<<endl;
    if(geShu*changDu==zong)
        return true;
    for(int i=cur;i<n;i++){
        if(panDuan[i])
            continue;
//        if(i&&!panDuan[i-1]&&muBang[i]==muBang[i-1])
//            continue;
        if(now+muBang[i]==changDu){
            panDuan[i]=1;
            if(slove(0,geShu+1,0))
                return true;
            panDuan[i]=0;
            return false;
        }
        else if(now+muBang[i]<changDu){
            panDuan[i]=1;
            if(slove(now+muBang[i],geShu,i+1))
                return true;
            panDuan[i]=0;
            if(now==0)
                return false;
        }
    }
    return false;
}