Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to ...
Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.Output
The output should contains the smallest possible length of original sticks, one per line.Sample Input
9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0
Sample Output
6 5
題意：將一組等長木棒隨機截斷，知道截斷後所有木棒長度，求截斷前等長木棒最小長度
思路：從小到大枚舉原長（從長度最長的木棍開始），DFS+剪枝
先求和，用總和除以原長得到需要拼湊的木棍數量，進行dfs判斷可行性
剪枝1：從長到短排序木棍，以便於優先用少量長木棍達到目標，減少dfs次數
剪枝2：當拼湊一根等長木棍時，當前沒用過的最長的木棍一定會成為第一個（因為每次的拼湊策略總會選擇比上一個選擇木棍短的棍子，如果沒有選當前最長，說明當前最長一定不能當一組方案中的次長木棍）
剪枝3：每一次只考慮比上一次選擇更短的木棍，因為比上一次選擇更長的木棍已經考慮過。
剪枝4：當一次拼湊有多個相同長度木棍可選時，只選擇其中的一個進行搜索，以避免重覆搜索
剪枝5：沒有必要用完所有的小棒拼出完整的m根等長木棒，只需要拼出m-1根，因為剩下的小棒無論如何是可以拼成的
（剪枝6：如果當前已拼湊的長度加上所有輸入數據的最小值還是大於要求的等長木棒長度，直接返回不可能。）
代碼（吐槽一下大多數16ms題解沒優化完全)（0ms通過)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<deque> #include<queue> #include<vector> #include<numeric> using namespace std; #define f(i,j) for(int i=1;i<=j;i++) #define fx(i,k,j) for(int i=k;i<=j;i++) #define gi(i) scanf("%d",&i) #define gii(i,j) scanf("%d%d",&i,&j) #define gi(i) scanf("%d",&i) #define giii(i,j,k) scanf("%d%d%d",&i,&j,&k) #define pi(i) printf("%d\n",i) #define pii(i,j) printf("%d %d\n",i,j) #define pf printf #define inf 0x3f3f3f3f #define clr(a) memset(a,0,sizeof(a)) #define fill(a,b) memset(a,b,sizeof(a)) #define _inline __attribute__((always_inline)) inline typedef long long LL; int n; int vis[65]; int p[65]; int L; int ndl; int dfs(int tot,int stk,int sta){ if(stk==ndl) return 1; if(tot==L) return dfs(0,stk+1,0); if(tot==0) sta=2; int last=0; if(tot+p[n]>L) return 0; fx(i,sta,n){ if(!vis[i] && p[i]+tot<=L && p[i]!=last){ last=p[i]; vis[i]=1; if(dfs(tot+p[i],stk,i+1)) return 1; vis[i]=0; if(tot==0) return 0; } } return 0; } int main(){ while(gi(n)!=EOF){ if(!n) return 0; f(i,n) gi(p[i]); sort(p+1,p+1+n,greater<int>()); int MX=accumulate(p+1,p+1+n,0); int ans=-1; int M2=MX>>1; for(int i=p[1];i<=M2;i++){ if(MX%i!=0) continue; L=i; ndl=MX/i-1; clr(vis); vis[1]=1; if(dfs(p[1],0,2)){ ans=i; break; } } pi(ans==-1?MX:ans); } }
