【題目描述】

喬治有一些同樣長的小木棍，他把這些木棍隨意砍成幾段，直到每段的長都不超過50。現在，他想把小木棍拼接成原來的樣子，但是卻忘記了自己開始時有多少根木棍和它們的長度。給出每段小木棍的長度，編程幫他找出原始木棍的最小可能長度。

【輸入】

第一行為一個單獨的整數N表示砍過以后的小木棍的總數，其中N≤60，第二行為N個用空個隔開的正整數，表示N根小木棍的長度。

【輸出】

僅一行，表示要求的原始木棍的最小可能長度。

【輸入樣例】

9
5 2 1 5 2 1 5 2 1

【輸出樣例】

6

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 1000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; int a[N]; bool vis[N]; int cnt; bool cmp(int x,int y){return x>y; } bool dfs(int k,int step,int rest,int len){//k為已經拼接好的個數,step為上一個的編號,rest為剩余的長度,len為木棍的長度if(k==cnt+1 && rest==0)//拼接好個數為要求數且無剩余return true;else if(k==cnt+1)//拼接好個數為要求數但有剩余return false;else if(rest==0){//拼接好個數不為要求數但無剩余，重新開始rest=len;//剩余數變為長度step=0;//編號歸零}for(int i=step+1;i<=cnt;i++){if(!vis[i]){if(rest-a[i]>=0){//保證剩余值不為負數vis[i]=true;if(dfs(k+1,i,rest-a[i],len))return true;vis[i]=false;if(a[i]==rest || len==rest)//頭尾剪枝，此時已在回溯之后，需要判斷頭尾兩種情況break;while(a[i]==a[i+1])//去重剪枝，用當前長度搜索無結果時，對同樣長度的可以忽略i++;}}}return 0; } int main(){int n;scanf("%d",&n);int sum=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(x<=50){a[++cnt]=x;sum+=x;}}sort(a+1,a+1+cnt,cmp);for(int i=a[1];i<=sum;i++){if(sum%i==0){if(dfs(1,0,i,i)){printf("%d\n",i);break;}}}return 0; }

?

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的小木棍（信息学奥赛一本通-T1442）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。