P1120 小木棍 ［数据加强版］

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1120


题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过5050。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入输出格式
输入格式：
共二行。

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）

第二行为N个用空个隔开的正整数，表示N根小木棍的长度。

输出格式：
一个数，表示要求的原始木棍的最小可能长度

输入输出样例
输入样例#1：
9
5 2 1 5 2 1 5 2 1
输出样例#1：
6
说明
2017/08/05

数据时限修改：

-#17 #20 #22 #27 四组数据时限500ms500ms
-#21 #24 #28 #29 #30五组数据时限1000ms1000ms
其他时限改为200ms200ms（请放心食用）

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<cstdlib>
   
3. #define FOR(i,a,b) for(register int i=a;i<=b;i++)
   
4. #define ROF(i,a,b) for(register int i=a;i>=b;i--)
   
5. using namespace std;
   
6. const int N=70;
   
7. int n,l[N],len,temp,minn=0x7fff,maxn;
   
8. void dfs(int e,int sum,int res,int p)
   
9. {
   
10.     if(!res)
    
11.     {
    
12.         cout<<e<<endl;
    
13.         exit(0);
    
14.     }
    
15.     if(sum==e)
    
16.     {
    
17.         dfs(e,0,res-1,maxn);
    
18.         return;
    
19.     }
    
20.     ROF(i,p,minn)
    
21.     {
    
22.         if(l[i] && i+sum<=e)
    
23.         {
    
24.             l[i]--;
    
25.             dfs(e,sum+i,res,i);
    
26.             l[i]++;
    
27.             if(sum==0 || sum + i==e)break;
    
28.         }
    
29.     }
    
30.     return;
    
31. }
    
32. int main()
    
33. {
    
34.     cin>>n;
    
35.     FOR(i,1,n)
    
36.     {
    
37.         cin>>temp;
    
38.         if(temp>50)continue;
    
39.         l[temp]++;len+=temp;
    
40.         minn=min(minn,temp);
    
41.         maxn=max(maxn,temp);
    
42.     }
    
43.     temp=len>>1;
    
44.     FOR(i,maxn,temp)
    
45.         if(len%i==0)dfs(i,0,len/i,maxn);
    
46.     cout<<len<<endl;
    
47.     return 0;
    
48. }
    

复制代码