洛谷P1120 小木棍

url: https://www.luogu.com.cn/problem/P1120

tag:
枚举，搜索，剪枝，dfs

思路：
先从大到小排序，并计算全部木棍长度的和。之后从最长的木棍长开始一直到和的一半枚举，作为原来木棍的长度。然后拿到这个原来的长度之后dfs一下看在有限段的情况下能不能拼凑出全部木棍，可以就输出。最后枚举完全部可能结果后都没答案，就输出长度和作为结果，表示原来只有一根木棍。参考： https://www.luogu.com.cn/article/fxoshw2y

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70;
int n, len, m, sum;
int a[N];
int nxt[N];
bool flag = false;
bool st[N];
bool cmp (int &a, int &b)
{
    return a > b;
}
void dfs(int k, int last, int rest)
{
    int i;
    if (!rest) {
        if (k == m)
        {
            flag = true;
            return;
        }
        for (i = 0; i < n; i ++) if (!st[i]) break;
        st[i] = true;
        dfs(k + 1, i, len - a[i]);
        st[i] = false;
        if (flag) return;
    }
    int l = last + 1, r = n - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] <= rest) r = mid;
        else l = mid + 1;
    }
    for (i = l; i < n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs(k, i, rest - a[i]);
            st[i] = false;
            if (flag) return;

            if (rest == a[i] || rest == len) return;
            i = nxt[i];
            if (i == n - 1) return;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a + n, cmp);
    nxt[n - 1] = n;
    for (int i = n - 2; i >= 0; i --)
    {
        if (a [i] == a[i + 1]) nxt[i] = nxt[i + 1];
        else nxt[i] = i;
    }
    for (len = a[0]; len <= sum / 2; len ++)
    {
        if (sum % len != 0) continue;
        m = sum / len;
        st[0] = true;
        dfs(1, 0, len - a[0]);
        st[0] = false;
        if (flag)
        {
            cout << len << endl;
            return 0;
        }
    }
    cout << sum << endl;
    return 0;
}