POJ ( acm.pku.edu.cn ) 1011

剪枝，深搜，that's it.

#include <memory.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int  g_sticks[65];
bool g_used[65];
int  g_length;
int  g_sum;
int  g_max;
int  g_min;
int  g_target;

bool dfs(int target, int remained, int begin) {
 if( target<g_min||begin>=g_length )
     return false;
 if (target==g_target) { //第一根
     for (int i=begin;i<g_length;++i) {
         if (g_used[i])
             continue;
         g_used[i]=true;
         if(g_sticks[i]==target){ // 最后一根
             if(remained==1)
                 return true;
             if(dfs(g_target , remained-1, 1))
                 return true;
             g_used[i]=false;
             return false;
         } else if (dfs(target-g_sticks[i],remained,i+1))
             return true;
         g_used[i]=false;
         return false;
     }
 } else {
     for (int i=begin;i<g_length;++i) {
         if (g_used[i])
             continue;
         if (g_sticks[i]>target)
             continue;
         g_used[i]=true;
         if(g_sticks[i]==target){ // 最后一根
             if(remained==1)
                 return true;
             if(dfs(g_target , remained-1, 1))
                 return true;
             g_used[i]=false;
             return false;
         }
         if (dfs(target-g_sticks[i],remained,i+1))
             return true;
         g_used[i]=false;
         for(;g_sticks[i]==g_sticks[i+1];++i);
     }
 }
 return false;
}

//#include <fstream>
int main() {
//    ifstream fin("test.txt");
 istream& xin=cin;
 for (;xin>>g_length&&g_length;) {
     int x;
     bool succeed=false;
     g_max=g_sum=0;
     g_min=1000;
     for (int i=0;i<g_length;++i) {
         xin>>x;
         g_sticks[i]=x;
         g_sum+=x;
         if (x>g_max) g_max=x;
         if (x<g_min) g_min=x;
         g_used[i]=false;
     }
     sort(g_sticks,g_sticks+g_length,greater<int>());
     g_sticks[g_length]=0;
     g_used[g_length]=true;
     for (int j=g_max;j<=g_sum/2;++j) {
         if (g_sum%j==0) {
             g_target=j;
             if ( dfs(j,g_sum/j,0) ) {
                 cout<<j<<endl;
                 succeed=true;
                 break;
             }
         }
     }
     if (!succeed)
         cout<<g_sum<<endl;
 }
 return 0;
}

看完整版本就知道我下了多大功夫了：

#if 1 // includes
#include <memory.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#endif   //  for folding

#define POJ_IS_STUPID 0
#if     POJ_IS_STUPID
#if 0

struct state { //里面这些东西不一定都用得着倒是了
    int sticks[51];  // 长度为 i 的木棍有 sticks[i] 个。
    int figures[51]; // 各种长度
    int nfigures;
    int length;
    int target;
    int remained;
    int max;
    int min;
    int sum;
};
template <class T>
size_t inv_bin_search(T* array, size_t len, T const& n) {
    size_t a=0,b=len,m1,m2=-1;
    for (m1=(a+b)>>1;m1!=m2;) {
        m2=m1;
        if     (array[m1]==n) return m1;
        else if (array[m1]>n)  a=m1;
        else b=m1;
        m1=(a+b)>>1;
    }
    if (array[m1]<n) return m1;
    else return m1-1;
}

bool match(state& st, int target) {
    bool first=(target==st.target);
    int i,*j;
    if (target>st.max) {
        //for(i=st.max;i>=st.min;--i){
        for (j=st.figures;i=*j;++j) {
            if (st.sticks[i]) {
                --st.sticks[i];
                st.sum-=i;
                if (match(st,target-i))
                    return true;
                st.sum+=i;
                ++st.sticks[i];
                if (first)
                    return false;
            }
        }
        return false;
    } else if (target<st.min) {
        return false;
    } else if (target>st.sum) {
        return false;
    } else if (target==st.sum) {
        return true;
    }
    if (st.sticks[target]) {
        --st.sticks[target];
        st.sum-=target;
        if (--st.remained==0) return true;
        if (match(st,st.target))
            return true;
        ++st.remained;
        st.sum+=target;
        ++st.sticks[target];
        return false;
    }
    for (j=st.figures+inv_bin_search<int>(st.figures,st.nfigures,target);
        *j>=target&&*j;++j);
    for (;i=*j;++j) {
        if (st.sticks[i]) {
            --st.sticks[i];
            st.sum-=i;
            if (match(st,target-i))
                return true;
            st.sum+=i;
            ++st.sticks[i];
            if (first)
                return false;
        }
    }
    return false;
}

int main() {
    for (state s={{0},{0},0,0};cin>>s.length&&s.length;) {
        s.sum=0;
        s.max=0;
        s.min=100;
        int x,i,j,n=0;
        bool succeed=false;
        for (i=0;i<=50;++i)
            s.sticks[i]=0;
        for (i=0;i<s.length;++i) {
            cin>>x;
            if (!s.sticks[x]) {
                s.figures[n]=x;
                ++n;
            }
            ++s.sticks[x];
            s.sum+=x;
            if (x>s.max) s.max=x;
            if (x<s.min) s.min=x;
        }
        s.figures[n]=0;
        s.nfigures=n;
        sort(s.figures,s.figures+n,greater<int>());
        for (j=s.max;j<=s.sum/2;++j) {
            if (s.sum%j==0) {
                s.target=j;
                s.remained=s.sum/j;
                if ( match(s,j) ) {
                    cout<<j<<endl;
                    succeed=true;
                    break;
                }
            }
        }
        if (!succeed)
            cout<<s.sum<<endl;
    }
    return 0;
}

#else

struct state { //里面这些东西不一定都用得着倒是了
  int sticks[51];  // 长度为 i 的木棍有 sticks[i] 个。
  int figures[51]; // 各种长度
  int nfigures;
  int length;
  int target;
  int remained;
  int max;
  int min;
  int sum;
};
template <class T>
size_t inv_bin_search(T* array, size_t len, T const& n) {
  size_t a=0,b=len,m1,m2=-1;
  for (m1=(a+b)>>1;m1!=m2;) {
      m2=m1;
      if     (array[m1]==n) return m1;
      else if (array[m1]>n)  a=m1;
      else b=m1;
      m1=(a+b)>>1;
  }
  if (array[m1]<n) return m1;
  else return m1-1;
}

bool match(state& st, int target) {
  int (&sticks)[51]=st.sticks;
  int (&figures)[51]=st.figures;
  int &sum=st.sum;
  int &remained=st.remained;
  bool first=(target==st.target);
  int i,*j;
  if (target>st.max) {
      //for(i=st.max;i>=st.min;--i){
      for (j=figures;i=*j;++j) {
          if (sticks[i]) {
              --sticks[i];
              sum-=i;
              if (match(st,target-i))
                  return true;
              sum+=i;
              ++sticks[i];
              if (first)
                  return false;
          }
      }
      return false;
  } else if (target<st.min) {
      return false;
  } else if (target>st.sum) {
      return false;
  } else if (target==st.sum) {
      return true;
  }
  if (sticks[target]) {
      --sticks[target];
      sum-=target;
      if (--remained==0) return true;
      if (match(st,st.target))
          return true;
      ++remained;
      sum+=target;
      ++sticks[target];
      return false;
  }
  for (j=figures+inv_bin_search<int>(figures,st.nfigures,target);
      *j>=target&&*j;++j);
  for (;i=*j;++j) {
      if (sticks[i]) {
          --sticks[i];
          sum-=i;
          if (match(st,target-i))
              return true;
          sum+=i;
          ++sticks[i];
          if (first)
              return false;
      }
  }
  return false;
}

int main() {
  for (state s={{0},{0},0,0};cin>>s.length&&s.length;) {
      s.sum=0;
      s.max=0;
      s.min=100;
      int x,i,j,n=0;
      bool succeed=false;
      for (i=0;i<=50;++i)
          s.sticks[i]=0;
      for (i=0;i<s.length;++i) {
          cin>>x;
          if (!s.sticks[x]) {
              s.figures[n]=x;
              ++n;
          }
          ++s.sticks[x];
          s.sum+=x;
          if (x>s.max) s.max=x;
          if (x<s.min) s.min=x;
      }
      s.figures[n]=0;
      s.nfigures=n;
      sort(s.figures,s.figures+n,greater<int>());
      for (j=s.max;j<=s.sum/2;++j) {
          if (s.sum%j==0) {
              s.target=j;
              s.remained=s.sum/j;
              if ( match(s,j) ) {
                  cout<<j<<endl;
                  succeed=true;
                  break;
              }
          }
      }
      if (!succeed)
          cout<<s.sum<<endl;
  }
  return 0;
}

#endif
#else
#if 0 //以前的

struct state { //不想用全局变量, 又不应该在递归的函数中使用太多参数, so...
    int  sticks[65];
    bool thereis[65];
    int  length;
    int  sum;
    int  max;
    int  target;
};

bool dfs(state& st, int target, int nremained, int begin=0) {
    if ( target==0 ) {
        if ( nremained==1 )
            return true;
        else
            return dfs(st,st.target,nremained-1,1);
    } else {
        if (begin>=st.length)
            return false;
        bool first=(target==st.target),last=false;
        for (int i=begin;i<st.length;++i) {
            if (!st.thereis[i])
                continue;
            if (st.sticks[i]>target) {
                // if(first){return false;}//impossible
                continue;
            }
            st.thereis[i]=false;
            last=(st.sticks[i]==target);
            if (dfs(st,target-st.sticks[i],nremained,i+1)) {
                return true;
            } else {
                st.thereis[i]=true;
                if ( first||last ) return false;
                for (;st.sticks[i]==st.sticks[++i];);
                --i;
            }
        }
    }
    return false;
}

int main() {
    for (state s;cin>>s.length&&s.length;) {
        s.max=s.sum=0;
        int x;
        bool succeed=false;
        for (int i=0;i<s.length;++i) {
            cin>>x;
            s.sticks[i]=x;
            s.sum+=x;
            if (x>s.max) s.max=x;
            s.thereis[i]=true;
        }
        sort(s.sticks,s.sticks+s.length,greater<int>());
        s.sticks[s.length]=0;
        s.thereis[s.length]=false;
        for (int j=s.max;j<=s.sum/2;++j) {
            if (s.sum%j==0) {
                s.target=j;
                if ( dfs(s,j,s.sum/j) ) {
                    cout<<j<<endl;
                    succeed=true;
                    break;
                }
            }
        }
        if (!succeed)
            cout<<s.sum<<endl;
    }
    return 0;
}

#else

int  g_sticks[65];
bool g_used[65];
int  g_length;
int  g_sum;
int  g_max;
int  g_min;
int  g_target;

bool dfs(int target, int remained, int begin) {
  if( target<g_min||begin>=g_length )
      return false;
  if (target==g_target) { //第一根
      for (int i=begin;i<g_length;++i) {
          if (g_used[i])
              continue;
          g_used[i]=true;
          if(g_sticks[i]==target){ // 最后一根
              if(remained==1)
                  return true;
              if(dfs(g_target , remained-1, 1))
                  return true;
              g_used[i]=false;
              return false;
          } else if (dfs(target-g_sticks[i],remained,i+1))
              return true;
          g_used[i]=false;
          return false;
      }
  } else {
      for (int i=begin;i<g_length;++i) {
          if (g_used[i])
              continue;
          if (g_sticks[i]>target)
              continue;
          g_used[i]=true;
          if(g_sticks[i]==target){ // 最后一根
              if(remained==1)
                  return true;
              if(dfs(g_target , remained-1, 1))
                  return true;
              g_used[i]=false;
              return false;
          }
          if (dfs(target-g_sticks[i],remained,i+1))
              return true;
          g_used[i]=false;
          for(;g_sticks[i]==g_sticks[i+1];++i);
      }
  }
  return false;
}

#include <fstream>
int main() {
  ifstream fin("test.txt");
  istream& xin=fin;
  for (;xin>>g_length&&g_length;) {
      int x;
      bool succeed=false;
      g_max=g_sum=0;
      g_min=1000;
      for (int i=0;i<g_length;++i) {
          xin>>x;
          g_sticks[i]=x;
          g_sum+=x;
          if (x>g_max) g_max=x;
          if (x<g_min) g_min=x;
          g_used[i]=false;
      }
      sort(g_sticks,g_sticks+g_length,greater<int>());
      g_sticks[g_length]=0;
      g_used[g_length]=true;
      for (int j=g_max;j<=g_sum/2;++j) {
          if (g_sum%j==0) {
              g_target=j;
              if ( dfs(j,g_sum/j,0) ) {
                  cout<<j<<endl;
                  succeed=true;
                  break;
              }
          }
      }
      if (!succeed)
          cout<<g_sum<<endl;
  }
  return 0;
}

#endif
#endif