长沙旅游网站建设,网站管理员登陆后缀,网站建设方案200字,建设网站域名167. 木棒 - AcWing题库
乔治拿来一组等长的木棒#xff0c;将它们随机地砍断#xff0c;使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态#xff0c;但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序#xff0…167. 木棒 - AcWing题库
乔治拿来一组等长的木棒将它们随机地砍断使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据每组数据包括两行。
第一行是一个不超过 64 的整数表示砍断之后共有多少节木棍。
第二行是截断以后所得到的各节木棍的长度。
在最后一组数据之后是一个零。
输出格式
为每组数据分别输出原始木棒的可能最小长度每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于 50。
输入样例
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0输出样例
6
5 解析
本题是一道经典的dfs剪枝题主要有三种剪枝 剪枝 1sum % length 0 只有 length是 sum的约数才有可能凑出多个等长的木棒 剪枝 2优化搜索顺序木棍长度从大到小排序可以减少搜索的分支 排除等效冗余优化 剪枝 3-1确定每根木棒中木棍的枚举顺序因为我们的方案和顺序没有关系以组合的形 式枚举方案可以少搜很多重复方案 剪枝 3-2如果当前木棍没有搜到方案则跳过所有长度相等的木棍 剪枝 3-3如果是木棒的第一根木棍就搜索失败了则一定搜不到方案 剪枝 3-4如果是木棒的最后一根木棍 上它木棒长度正好是 length搜索失败了也一 定搜不到方案 可以想想怎么证明上述几种剪枝的正确性dfs和动态规划很像
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
using namespace std;
const int N 70;
int n;
int ar[N],vis[N], len, sum;int cmp(const int a, const int b) {return a b;
}bool dfs(int u, int s,int start) {/*cout KKKKKKKKKKKKKKKKK len s endl;for (int i 1; i n; i) {cout vis[i] ;}cout endl endl;*/if (u * len sum) {/*cout _______________ u endl;*/return 1;}if (s len) {return dfs(u 1, 0, 0);/*if (dfs(u 1, 0, 0)) {cout LLLLLLLLLLLLL 1 endl;return 1;}*/}for (int i start; i n; i) {if (vis[i])continue;if (s ar[i] len)continue;vis[i] 1;if (dfs(u, s ar[i], i 1))return 1;vis[i] 0;if (s 0 || s ar[i] len)return 0;int j i;while (j n ar[j] ar[i])j;i j - 1;}return 0;
}int main() {while (cin n, n) {int mx 0;sum 0;for (int i 1; i n; i) {scanf(%d, ar[i]);sum ar[i];mx max(mx, ar[i]);}memset(vis, 0, sizeof vis);sort(ar 1, ar 1 n, cmp);len mx;while (1) {while (sum % len ! 0)len;//cout len endl;if (dfs(0, 0, 1)) {printf(%d\n, len);break;}len;}}return 0;
}
