题目传送：Sticks
思路：DFS + 剪枝
AC代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;int s[65];int vis[65];int n; int sum;int len;int flag;bool cmp(int a, int b) {return a > b;}void dfs(int cnt, int l, int pos) {//cnt表示现在选了的木条数，，l表示正在选的木条的总长度，pos表示下一个开始选的木条的下标 if(flag) return;if(l == 0) {//当前状态还没选木条 for(int i = 0; i < n; i ++) {if(!vis[i]) {vis[i] = 1;dfs(cnt + 1, s[i], i + 1);vis[i] = 0;break;}} }else if(l == len) {//当前状态的长度满足初始长度，则找到一组符合的 if(cnt == n) flag = 1;//全部都找到了 else dfs(cnt, 0, 0);//继续找 }else {//当前状态木条总长度没选够，继续选 for(int i = pos; i < n; i ++) {if(!vis[i] && l + s[i] <= len) {if(!vis[i – 1] && s[i] == s[i-1]) continue;//去重剪枝，不剪枝对于最坏情况会超时vis[i] = 1;dfs(cnt + 1, l + s[i], i + 1);vis[i] = 0;}}}}int main() {while(scanf("%d", &n) != EOF) {if(n == 0) break;sum = 0;for(int i = 0; i < n; i ++) {scanf("%d", &s[i]);sum += s[i];}sort(s, s + n, cmp);//从大到小排序，必须要先选大的，再选小的，否则会出错flag = 0;for(len = s[0]; len <= sum; len ++) {//依次枚举长度if(sum % len == 0) {//当长度满足整除sum才可以进行dfsmemset(vis, 0, sizeof(vis));dfs(0, 0, 0);if(flag) {cout << len << endl;//找到则输出，跳出循环break;}}}}return 0;}
带着感恩的心启程，学会爱，爱父母，爱自己，爱朋友，爱他人。
