吴队长征婚

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/61

Description

吴队长征婚这件事因为请客而没有传出去(虽然他忘了请一个队吃饭)，于是吴队长高兴地玩起了木棒。吴队长拿了一些长度相同的木(guang)棒(gun)，随机的把它们截成了N段，每一段最长50。现在他想把这些木棒还原成原来的状态，但是他忘记了原来的木棒有多少根，也忘记了每一根有多长。请帮助他设计一个程序，帮他计算之前木棒可能的最小长度。输入数据保证每一段木棒长度都大于0。

Input

输入有多组数据，每组数据分为两行。
第一行一个整数N，表示截断之后木棒的个数。1≤N≤64
第二行N个整数，表示截断之后的每一段小木棒的长度。当N=0时，表示输入结束。

Output

每组数据输出一个整数占一行，表示原木棒可能的最小长度。

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

HINT

题意

题解：

爆搜题
剪枝1：大木棍长度只可能是sum的约数
剪枝2：重复的木棍就可以不用枚举了
剪枝3：每次都从最长的开始枚举
然后就可以AC了……

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

int a[],n,sum,num;

int vis[];

bool cmp(int aa,int bb)

{

    return aa>bb;

}

int dfs(int x,int y,int z,int len)

{

    if(x==num)

        return ;

    for(int i=z+;i<n;i++)

    {

        if(vis[i])

            continue;

        if(y+a[i]==len)

        {

            vis[i]=;

            if(dfs(x+,,-,len))

                return ;

            vis[i]=;

            return ;

        }

        else if(y+a[i]<len)

        {

            vis[i]=;

            if(dfs(x,y+a[i],i,len))

                return ;

            vis[i]=;

            if(y==)

                return ;

            while(a[i]==a[i+])

                i++;

        }

    }

    return ;

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        if(n==)

            break;

        sum=;

        for(int i=;i<n;i++)

        {

            scanf("%d",&a[i]);

            sum+=a[i];

        }

        sort(a,a+n,cmp);

        int i;

        for(i=a[];i<=sum;i++)

        {

            if(sum%i==)

            {

                num=sum/i;

                memset(vis,,sizeof(vis));

                if(dfs(,,-,i))

                    break;

            }

        }

        printf("%d\n",i);

    }

}

吴队长

2015 UESTC 搜索专题E题 吴队长征婚 爆搜