pku1011 Sticks

digiter

一直没想好怎么搜索，所以一直没写，最近看到一段细节写得非常好的代码，于是把这道题AC了，感觉这段搜索写得灰常强大，短而效率高
#include <cstdio>#include <algorithm>#include <functional>using namespace std;const int maxN = 64 + 5;int n, stick[maxN], len, m;bool used[maxN] = {false}, done;void dfs(int k, int now, int cnt){if (cnt == m)done = true;else if (now == len)dfs(0, 0, cnt + 1);else {int pre = -1;for (int i = k; i < n; ++i)if (!used && stick != pre && now + stick <= len){used = true;pre = stick;dfs(k + 1, now + stick, cnt);used = false;if (k == 0 || done)return;}}}int main(){while (scanf("%d", &n), n > 0){int sum = 0;for (int i = 0; i < n; ++i){scanf("%d", &stick);sum += stick;}sort(stick, stick + n, greater<int>());done = false;for (len = stick[0]; len <= sum; ++len)if (sum % len == 0){m = sum / len;dfs(0, 0, 0);if (done)break;}printf("%d\n", len);}return 0;}

原代码的地址是
http://www.cnblogs.com/lotus3x/archive/2008/07/25/1251552.html