洛谷P1120 小木棍［数据加强版］(回溯法)
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式：
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出格式：
输出文件仅一行，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例：
9
5 2 1 5 2 1 5 2 1
输出样例：
6
说明
2017/08/05
数据时限修改：
-#17 #20 #22 #27 四组数据时限500ms
-#21 #24 #28 #29 #30五组数据时限1000ms
其他时限改为200ms（请放心食用）
解题分析
采用回溯法，对不同可能的长度进行尝试，即对与一个原始木棍的可能的长度d，对每一个木棍进行拼接，如果最后能够将所有木棍都拼接到一个长度为d的木棍中，则d就是可能的结果，所有可能的结果中，最小值即为最终结果。
可以进行下列优化或剪枝：
1、将所有小木棍按长度从大到小排序。
2、小木棍的可能长度为所有小木棍总长度的一个约数，因此求出总长度的大于小木棍最长长度的所有约数，并按照从小到大排序，依次作为原始木棍的可能长度d，进行尝试拼接，如果成功，则输出结果，后面不再进行尝试。
3、对于给定的可能长度d，从长度最大的小木棍开始配对，在配对时，从长度较大小木棍的开始（注意，不能从长度小的开始配对，否则会增加回退的次数），如果配对成功，则在从下一个小木棍开始配对，直到所有木棍都配对成功或某一个没有配对成功为止。
4、如果从某一个木棍开始配对没有成功，则说明该可能的长度不合法，进行下一个可能的长度的尝试。
5、如果对于从某个长度d1开始的木棍开始的配对，当配对到第k个小木棍时，发现不能成功配对，则对于k以后的与k同等长度的小木棍肯定也不能成功，因此这些木棍可以不需要再尝试。
6、如果在尝试过程中，发现将剩下的小木棍都拼接到当前木棍中也不能达到预定的长度，则直接退出尝试。
#include
#include
#include
#include
#include
#include
#include
using namespace std; #define N 67 int n = 0, tot=0, stick[N], pos[200], cnt = 0, used[N], flag = 0; int sum_a[N]; void get_i(int &x){ char ch = getchar(); x = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); } } // pos:当前配对的目标长度；start: 本轮配对的起点；len：到目前位置已配对的长度； // start_left:本次配对的的起点，与start的区别是，start为本轮配对的第一个小木棍的位置 // step：本轮配对的次数，如果step为0，则说明本轮配对失败 void resolve(int pos, int start, int len, int start_left, int step){ int i, j, check_n; if(flag || len > pos || sum_a[n-1] - sum_a[start] < pos - len - stick[start]) // 优化6 return; if(tot == n){ cout<
<
pos) continue; used[i] = 1; tot++; step++; resolve(pos, start, stick[i]+len, i+1, step); step--; used[i] = 0; tot--; if(stick[i]+len == pos || step == 0) // 优化4，已回退到上一个成功的配对，说明本次配对不可能成功 return; while(stick[i]==stick[i+1]) i++; // 优化5 } } } int main(){ ios::sync_with_stdio(false); int i, j, m, x, sum1[51]={0}; get_i(m); for(i=0; i
50) continue; if(n==0) sum_a[0] = x; else sum_a[n] = sum_a[n-1] + x; stick[n++] = x; tot += x; } sort(stick, stick+n, greater
()); // 优化1 // 优化2：确定可能的长度，为tot的不小于最长小木棍的因子 for(i=stick[0]; i<=tot/2; i++){ if(tot%i == 0) pos[cnt++] = i; } pos[cnt++] = tot; // 加上最长的长度 // 优化2：从小到大对每一种个可能情形进行枚举 for(i=0; i