做完这道题，我的内心是崩溃的 QAQ
坑点1：最开始我枚举的是小木棍，因为不会剪枝，过不了。后来改成了枚举木棒。
坑点2：POJ上本题的数据是标准的（均不超过50）。但在acwing上本题有大于50的数据，需要在读入时跳过。
坑点3：代码36行的两个剪枝必须要有，否则就会超时（这道题的数据很强大，剪枝卡到极限了）
#include <bits/stdc++.h> using namespace std; int n, cnt, len, sum; // 小木棍，每根小木棍是否被使用过 int a[100], vis[100]; bool cmp(int a, int b) { return a > b; } // 已经拼好了几个木棒，当前木棒拼了多长，拼当前木棒上次使用的小木棍 bool dfs(int u, int state, int last) { // 拼成了目标个数 if (u == cnt) { return true; } // 当前木棒已经拼成 if (state == len) { return dfs(u + 1, 0, 0); } // 上次拼接失败使用的小木棍长度 int fail = 0; // 枚举小木棍 for (int i = last; i < n; i++) { if (vis[i] == 0 && state + a[i] <= len && fail != a[i]) { vis[i] = 1; if (dfs(u, state + a[i], i + 1)) { return true; } fail = a[i]; vis[i] = 0; // 1、尝试的第一根小木棍都失败，那么此小木棍拼接其他的木棒也会失败 // 2、如果正好能拼成len也失败，那么拼接其他的小木棍也会失败 if (state == 0 || state + a[i] == len) { return false; } } } return false; } int main(void) { int num, t; while (cin >> num && num) { n = sum = 0; for (int i = 0; i < num; i++) { cin >> t; // 跳过大于50的数据 if (t > 50) { continue; } a[n++] = t; sum += t; } sort(a, a + n, cmp); for (len = a[0]; len <= sum; len++) { if (sum % len == 0) { // 最后拼成多少根木棒 cnt = sum / len; // 初始化vis数组 memset(vis, 0, sizeof vis); // 如果能拼成 if (dfs(0, 0, 0)) { cout << len << endl; break; } } } } return 0; }