746
POJ1011-Sticks
SticksTime Limit 1000MS Memory Limit 10000K
Total Submissions 117588 Accepted 27100
Description
翻譯：
問題描述：喬治拿來一組等長的木棒，將它們隨機地裁斷，使得每一節木棒的長度都不超過50個長度單位。然後他又想把這些木棒恢複到為裁截前的狀態
，但忘記了木棒的初始長度。請你設計一個程序，幫助喬治計算木棒的可能最小長度。每一節木棒的長度都用大於零的整數表示
輸入：
由多個案例組成，每個案例包括兩行。第一行是一個不超過64的整數，表示裁截之後共有多少節木棒。第二行是經過裁截後，所得到的各節木棒的長度。
在最後一個案例之後，是零。
輸出：
為每個案例，分別輸出木棒的可能最小長度。每個案例占一行。
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5
解題思路
初始狀態：有N節木棒。最終狀態：這N節木棒恰好被拚接成若幹根等長的木棒。
從初始狀態到最終狀態最多有多少條不同的“路徑”(指原始單個木棒可能的長度）？
Sum/maxParts。其中Sum是全部N節木棒的長度之和，maxParts是最
長一節木棒的長度
。
每條“路徑”對應一個木棒的長度。從木棒長度最小的那條可能“路徑”開始，如果成功地的找到了這條“路徑”，就解決了問題DFS深搜
構造一條木棒長度為L的“路徑”：拚接木棒
在未被拚接的木棒中，找出一節最長的，開始拚接
從未拚接的木棒中，選擇一個長度合適的木棒，使得拚接後的木棒長度≤L1.找到了：
在前麵的拚接過程中曾試圖用過相同長度的一節其他木棒，但發現這樣拚接不成功，繼續尋找能夠進行拚接的木棒
把找到的那節木棒拚接上去。
繼續進行拚接 繼續拚接成功，找到了“路徑”
繼續拚接不成功，把剛拚接的那節木棒拿下來，繼續找下一個合適的未 拚接木幫2.沒有找到：拚接失敗
bool Dfs(int nUnusedSticks, int nLeft ) ;
表示: 當前有nUnusedSticks根未用木棒，而且當前正在拚的那根棍子比假定的棍子長度短了nLeft, 那麼在這種情況下能全部否拚成功。
AC代碼：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int len[100],flag[100],L;
int n,sum;
int cmp(int a,int b)
{
if(a!=b) return a>b;
}
int DFS(int num,int nLeft)
// nLeft表示當前正在拚的棍子和L比還缺的長度
{
int i;
if(num==0&&nLeft==0)
return 1;
if(nLeft==0)//一根剛剛拚完
nLeft=L;//開始拚新的一根
for(i=0;i<n;i++)
{
if(!flag[i]&&len[i]<=nLeft)//如果此棒沒有用過而且小於等於和L比還缺的長度
{
if(i>0)
{
if(flag[i-1]==0&&len[i]==len[i-1])
continue;//剪枝1
}
flag[i]=1;
if(DFS(num-1,nLeft-len[i]))
return 1;
else
{
flag[i] = 0;//說明不能用i作為
//第１條，
//那麼要拆以前的
//棍子，i還可能用
//在以前的棍子裏，
//因此要 flag[i]=0;
if(len[i]==nLeft||nLeft==L)
return 0;//剪枝2
}
}
}
return 0;
}
int main()
{
int i;
while(scanf("%d",&n)&&n)
{
sum=0;
memset(len,0,sizeof(len));
for(i=0;i<n;i++)
{
scanf("%d",&len[i]);
sum+=len[i];
}
sort(len,len+n,cmp);
for(L=len[0];L<=sum/2;L++)//從最長的那一根棒開始累加計算
{
if(sum%L)//木棒至少要有兩截
continue;
memset(flag,0,sizeof(flag));//記錄木棒是否被用過
if(DFS(n,L))
{
printf("%d\n",L);
break;
}
}
if(L>sum/2)
printf("%d\n",sum);//隻有一根木棒被剪成幾分
}
return 0;
}
最後更新：2017-04-03 08:26:14