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; } } } }