就是先std::sort，然后枚举可能的长棍长，如果是总长度的约数就DFS。

DFS的时候，长棍长度l固定，开始的时候剩余长度lea=l，top=n。

每次从top往下检查没有用过的棍子（也就是从长到短），从lea中截去最长的短棍p[i]。
截去p[i]之后，搜索lea-p[i],top=i.

如果lea=0了,让lea=l,top=n.



Submit>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>但是TLE了。code见下。


#include <cstdio>
#include <algorithm>
const int maxn=64;
int i,n,l,t,tmp,p[maxn],s[maxn];
bool u[maxn];
bool DFS(int depth,int lea,int top)
{
  if(depth==n) return true;
  if(lea>s[top]) return false;
  if(lea==0)
  {
    lea=l;
    top=n;
  }
  for(int i=top-1;i>=0;--i)
    if(u[i]&&p[i]<=lea)
    {
      u[i]=false;
      if(DFS(depth+1,lea-p[i],i)) return true;
      u[i]=true;
    }
  return false;
}
int main()
{
  for(;;)
  {
    scanf("%d",&n);
    if(n==0) return 0;
    for(t=i=0;i!=n;++i)
    {
      scanf("%d",&tmp);
      if(tmp<=50) t+=p[i]=tmp;
    }
    std::sort(p,p+n);
    s[0]=0;
    for(i=1;i!=n;++i) s[i]=s[i-1]+p[i-1];
    for(l=p[n-1];l!=t;++l)
      if(t%l==0)
      {
        memset(u,1,sizeof(u));
        if(DFS(0,0,0))
        {
          printf("%d\n",l);
          break;
        }
      }
  }
}

• Re:程序应该没有BUG，看来是剪枝的问题？如何剪呢？ (20) coder 2006-07-05 15:46:36
  • Re:程序应该没有BUG，看来是剪枝的问题？如何剪呢？ (39) Exile_oi 2006-07-05 21:03:49
• 好多层的递归啊 (0) yanical 2006-08-07 22:15:07