#题解#洛谷P1120 小木棍#搜索#剪枝

P1120 小木棍 - 洛谷

分析

1. 求最小可能长度len，我们从小到大枚举len，然后dfs搜索是否存在一种短棍的分配方法，使得每根长棍长度为len。

2. dfs(u,k,p)当前所拼长棍剩余长度u,剩余要拼的长棍个数k,当前可用短棍最长长度

3. 搜索剪枝：

4. sum==len * cnt;//sum为短棍长度和，cnt为长棍个数

5. 因为长度短的短棍更灵活，我们先把长度较长的短棍用完

6. 若某长棍第一个短棍选p（可用的最长）导致失败，那么该长棍第一个短棍要选长度小于p的

7. 若某长棍最后一个短棍选p导致失败，该长棍最后一个短棍要选更短的

代码实现

#include<bits/stdc++.h>
#define int  long long
#define endl '\n'
using namespace std;const int maxn = 66;
int n, sum, mx = maxn, d;
int len[maxn], a[maxn], pre[maxn];void dfs(int u, int k, int p)//当前长棍剩下u没拼，剩下k个长棍没拼，当前要拼地短棍长度（拼后是组成中最短）
{if (u == 0)//当前长棍拼好了，拼下一根{dfs(d, k - 1, a[n]);return ;}if (k == 0)//所有长棍拼好了，输出答案{cout << d;exit(0);}p = p < u ? p : u;//要拼地短棍不能比长棍剩余长度大while (p and len [p] == 0) //从p/u中较小地那个向下查询第一个出现的能用的短棍长度p--;while (p)if (len[p]){--len[p];dfs(u - p, k, p);++len[p];if (u == p or u == d)return ;//若用了p刚好拼完长棍但最终失败；；若该长棍的第一个短棍选择p但最终失败p = pre[p];}elsep = pre[p];
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1, x; i <= n; i++){cin >> x;sum += x;++len[a[i] = x];}sort(a + 1, a + 1 + n);for (int i = 1; i <= n; i++)if (a[i] != a[i - 1])pre[a[i]] = a[i - 1];for (d = a[n]; (d << 1) <= sum; ++d){if (sum % d) continue;dfs(d, sum / d, a[n]);}cout << sum;return 0;
}