UVa 307. Sticks

Description

George 拿了一些相同長度的棍子，然後隨意的把這些棍子切成一段一段的棍子（每段長度都不會超過 50 個單位長）。現在他想要把這些一段一段的棍子拼回原來的樣子，但是他忘了他原來帶多少根棍子來，並且也忘了原來每根棍子的長度。請幫助他設計一個程式算出這些棍子原來可能的最小長度。所有的棍子長度都是整數，並且大於 0。

Input Format

輸入含有多組測試資料。每組測試資料2列，第一列有一個整數 n 代表切後棍子的數目。第二列含有 n 個整數，分別代表這 n 支棍子的長度。
當 n=0 時代表輸入結束。

Output Format

對於每一列測試資料，輸出這些棍子原來可能的最小長度。

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

UVa - 307
翻譯來源：Luckycat

Solution

這題首先要考慮到「最小長度」所代表的意義，令最小長度為i、竿子長度總和sum
目前已知：
$i \in \lbrace x | 單一竿子最大長度 \le x \le sum \rbrace $
則可推論出以下結果

1. i絕對可以整除sum
2. 若 i > sum/2，則i必定為sum

利用以上推論結果去做DFS即可。
為了減少運算次數，所以會先取長度較長的竿子，這點需要注意。

Code

/*************************************************************************
  > File Name: 00307 - Sticks.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Fri Jun 29 12:16:42 2018
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;

int n;
int sticks[100];
bool use[100];
int len, sum;
bool cmp(int a, int b) {
    return a > b;
}
bool dfs(int i, int l, int r) {
    if (!l) {
        r -= len;
        if (!r)
            return true;
        for (i = 0; i < n && use[i]; i++);
        use[i] = 1;
        if (dfs(i, len - sticks[i], r)) return true;
        use[i] = 0;
        return false;
    }
    while (++i < n) {
        if (i && sticks[i - 1] == sticks[i] && !use[i - 1]) continue;
        if (sticks[i] > l || use[i]) continue;
        use[i] = 1;
        if (dfs(i, l - sticks[i], r)) return true;
        use[i] = 0;
        if (sticks[i] == l)
            break;
    }
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n && n) {
        sum = 0;
        bool flag = 1;
        for (int i = 0; i < n; i++) {
            cin >> sticks[i];
            sum += sticks[i];
        }
        memset(use, false, sizeof(use));
        sort(sticks, sticks + n, cmp);
        for (len = sticks[0]; len <= sum / 2 && flag; len++) {
            if (sum % len)
                continue;
            if (dfs(-1, len, sum)) flag = 0;
        }
        cout << (flag ? sum : len - 1) << '\n';
    }
    return 0;
}