Luogu P1120 小木棍 ［数据加强版］

　　看了题目心中只有一个字——搜索！！！

　　但是很显然，朴素的搜索（回溯）绝壁超时。

　　剪枝&优化（要搞很多，要不然过不了）

　　1：从小到大搜索它们的因数，这样找到就exit。

　　2：将数据从大到小排序，因为长的是肯定要选的，所以早点选可以减小接下来的可能。

　　3：如果一组它后面的几组都无法搜出，那么可以直接跳过这一长度。

　　4：如果一根木棍不行，那么和它相同长度的木棍肯定不行。

　　5：若在新一组的拼凑中，最大的木棍无法完成，则接下来的这几组都不行（因为那根最长的木棍是迟早要用的）。

　　然后就是一顿爆搜（代码挺短）

　　CODE

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=70;
int a[N],n,sum,i,tot,x,need;
bool f[N];
inline void read(int &x)
{
    x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int comp(int a,int b) { return a>b; }
void dfs(int m,int last,int sum,int cnt)
{
    if (cnt==need) { printf("%d",m); exit(0); }
    for (int i=last;i<=tot;++i)
    if (f[i]&&a[i]+sum<=m)
    {
        f[i]=0;
        if (a[i]+sum==m) dfs(m,1,0,cnt+1); else dfs(m,i+1,a[i]+sum,cnt);
        f[i]=1;
        if (sum+a[i]==m||!sum) break;
        while (a[i]==a[i+1]) i++;
    }
}
int main()
{
    read(n);
    for (i=1;i<=n;++i)
    {
        read(x);
        if (x>50) continue;
        a[++tot]=x;
        sum+=x;
    }
    sort(a+1,a+tot+1,comp);
    for (i=1;i<=sum;++i)
    if (!(sum%i)) 
    {
        memset(f,true,sizeof(f));
        need=sum/i;
        dfs(i,1,0,0);
    }
    return 0;
}