Respect2Dの日記

PKU : 1011 - Sticks

深さ優先探索

問題概要

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

「等しい長さ」の棒がいくつかあります.

これを長さが50以下になるように, N本の適当な長さの棒に分割しました.

分割されたN本の長さが入力されたとき, もともとの棒の長さの最小を求める問題です.

アルゴリズム

深さ優先探索で, 刈れる枝をがんばって刈る問題です.

TLEしたので, 刈り方は以下の方々の解説を参考にさせていただきました.

• id:kusano_progさん (http://d.hatena.ne.jp/kusano_prog/20091112/1258046742)
• id:atetubouさん (http://d.hatena.ne.jp/atetubou/20110725/1311602938)

ありがとうございます！

枝刈りのDFSは, すごく苦手です・・・.

プログラム

int n,sum,maxLen,len;
int t[100];
bool used[100];

bool dfs(int idx,int len_rem,int n_rem){
  int next_len = len_rem - t[idx];
  if(next_len == 0 && n_rem == 0) return true;
  if(n_rem == 0) return false;

  used[idx] = true;

  if(next_len == 0){
    int i = 0;
    while(used[i]) i++;
    if(dfs(i,len,n_rem-1)) return true;
  }
  else{
    int before = 0;
    for(int i=idx+1;i<n;i++){
      if(next_len < t[i] || used[i] || before == t[i]) continue;
      if(dfs(i,next_len,n_rem-1)) return true;
      before = t[i];
    }
  }

  used[idx] = false;

  return false;
}

int main(void){
  while(scanf("%d",&n),n){
    sum = 0;
    maxLen = 0;

    rep(i,n){
      scanf("%d",&t[i]);
      sum += t[i];
      maxLen = max(maxLen,t[i]);
    }

    sort(t,t+n,greater<int>());

    for(len=maxLen;;len++){
      if(sum % len != 0) continue;
      memset(used,0,sizeof(used));
      if(dfs(0,len,n-1)){
        printf("%d\n",len);
        break;
      }
    }
  }
}

Permalink | コメント(0) | トラックバック(0) | 14:18