敗戦記

PKU 1011 Sticks

PKU

http://poj.org/problem?id=1011

n本のスティックが与えられる。

このスティックはもとはある同じ長さの棒を適当に切って出来たものである。

もとの棒の長さとして考えられる最小の長さを求めろというような問題。

何回か挑戦して、ずっとTLEしまくって解けなかった問題です。

やっとこさ解けた感がありますね。

枝刈り深さ優先でやりました。

int in[64];
int sum;
bool use[64];
int n;

bool dfs(int tsum,int len,int ne,int lest){
  if(lest==0)return true;
  int be=0;
  for(int i=tsum?ne:0;i<n;++i){
    if(use[i] || be==in[i])continue;
    if(tsum+in[i]>len)continue;
    use[i]=true;
    if(dfs((tsum+in[i])%len,len,i+1,lest-1))return true;
    use[i]=false;
    be=in[i];
    if(tsum==0)return false;
  }
  return false;
}


main(){
  while(cin>>n,n){
    sum=0;
    memset(use,0,sizeof(use));
    int maxv=0;
    rep(i,n){
      cin>>in[i];
      sum+=in[i];
      maxv=max(in[i],maxv);
    }
    sort(in,in+n,greater<int>());
    for(int i=maxv;;++i){
      if(sum%i)continue;
      if(dfs(0,i,0,n)){
        cout<<i<<endl;
        break;
      }
    }
  }
}

Permalink | コメント(0) | トラックバック(1) | 23:08