小木棍

Description

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。 现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。 给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

Input

共有二行。 第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60，第二行为N个用空格隔开的正整数，表示N根小木棍的长度。

Output

仅一行，表示要求的原始木棍的最小可能长度。

Sample Input

9 5 2 1 5 2 1 5 2 1

Sample Output

6

Hint

把大于50的略去不管。

Source

搜索

Solution

枚举每一种可能的初始木棍长度，然后搜索，满足情况输出即可(还要加上一些神奇的剪枝)

Code

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <map> #include <vector> #include <queue> #define L 100 #define LL long long using namespace std; int n, x, a[L], sum, ave, len, cnt; bool vis[L], pd; inline bool comp(int x, int y) { return x > y; } inline void dfs(int tot, int l, int now) { if (pd) return ; if (tot == cnt && l == 0) {pd = true; return ;} int last = -1; for (int i = now; i <= cnt; ++i) if (!vis[i] && l + a[i] <= len) { if (l + a[i] == last) continue; last = l + a[i], vis[i] = true; if (l + a[i] == len) dfs(tot + 1, 0, 1); else dfs(tot + 1, l + a[i], i + 1); vis[i] = false; if (!l || l + a[i] == len) break; } } int main() { freopen("CJOJ1642.in", "r", stdin); freopen("CJOJ1642.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &x); if (x <= 50) a[++cnt] = x, sum += x; } sort(a + 1, a + 1 + cnt, comp); for (int i = a[1]; i <= sum; ++i) if (sum % i == 0) { len = i, dfs(0, 0, 1); if (pd) {printf("%d\n", i); return 0;} } return 0; }

Summary

一次性AC