小木棍（信息学奥赛一本通-T1442）

【题目描述】

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过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）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。