题目:P1120 [CERC 1995] 小木棍 - 洛谷

思路：要找到最少的能够将所有木棍拼为一个 cnt 个大小相等的木棍，所以最小长度 len 一定大于原数组中所有木棍的最大值，小于等于所有原数组的木棍大小的和，所以我们可以选择从数组最大值遍历到数组之和在这其中找到最小的符合题目要求的长度 len 。然后利用 dfs（深度优先搜索）去寻找在该长度下是否能够将木棍拼为 cnt 份，如果可以直接输出 len 结束程序。

但是，如果直接这样遍历的话时间复杂度是O(n!)是一定会超时的，因此需要有以下优化：

1、数组从大到小排序："大块优先"原则，在拼图问题中，大的木棒灵活性更差（能匹配的组合更少），所以应该先处理。

2、去除不可能完成拼图的情况：如果这个长度如果无法被数组元素的总和给整除，那么这个长度肯定是不合适的。

3、如果当前正在拼接一根新的木棒（h == 0），但尝试了某根木棒后失败，直接返回：因为所有木棒最终都要被使用，如果连最大的木棒都不能作为开头完成拼接，那更小的木棒作为开头就更不可能完成了。

4、如果当前木棒刚好能把当前这根棍子拼满（h + v[i] == len），但后续拼接失败，直接返回：如果刚好拼满都失败了，换其他方案更不可能成功。

5、跳过所有相同长度的木棒：相同长度的木棒在搜索中是完全对称的，如果第一个5不能解决问题，后面的5也不能，直接跳过就能能避免大量重复搜索。

以上就是这道题的基本思路了，但是这道题。。。。。。

这道题的最后一个测试点卡的实在是太死了，如果刚好是最后一个测试点过不了的话可以注意以下几个点：

  • 同步流关闭，并加上 cin.tie(0), cout.tie(0)

  • dfs函数前面加inline

  • 数组不要使用vector，改为最原始的数组

  • dfs函数参数最好少一点比较好 我之前用的void dfs(int i,int h,int u)直接给我超时了

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, cnt = 0,len;
int u = 1;
bool vis[66];
int v[66];

inline void dfs(int i,int h) {
    if (u == cnt) {
        cout << len << endl;
        exit(0);
    }
    if (h == len) {
        u++;
        dfs(1, 0);
        u--;
        return;
    }
    for (; i <= n; i++) {
        if (vis[i] || v[i] + h > len) continue;
        vis[i] = true;
        dfs(i + 1, v[i] + h);
        vis[i] = false;

        if (!h) return;
        if (v[i] + h == len) return;
        while (i < n && v[i] == v[i + 1]) i++;
    }
}

void solve() {
    cin >> n;
    int r = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        r += v[i];
    }
    sort(v + 1,v + n + 1, [&](const int& a, const int& b) {return a > b; });
    len = v[1];
    for (; len <= r; len++) {
        if (r % len != 0) continue;
        cnt = r / len;
        dfs(1, 0);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}