[题目链接]
http://poj.org/problem?id=1011
[算法]
深搜剪枝
首先我们枚举木棍的长度 i, 那么就有 s/i 根木棍, 其中 s 为木棍长度的总和, 朴素的做法就是对每种长度进行搜索, 然而这样是会超时的, 考虑优化 :
优化 1 : 优化搜索顺序, 将这些木棍的长度从大到小排序, 搜索时按递减的顺序选取木棍 (优先选择长的木棍)
优化 2 : 排除等效亢余, 对于每根木棒, 记录最近一次尝试的木棒, 如果有与最近一次同样长度的木棒, 则不尝试, 因为这必定也是失败的
优化 3 : 排除等效亢余, 如果一根木棒尝试的第一根木棍就失败了, 那么直接返回失败, 因为其它木棒如果选这根木棍同样是失败的
[代码]
- #include <algorithm>
- #include <bitset>
- #include <cctype>
- #include <cerrno>
- #include <clocale>
- #include <cmath>
- #include <complex>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <deque>
- #include <exception>
- #include <fstream>
- #include <functional>
- #include <limits>
- #include <list>
- #include <map>
- #include <iomanip>
- #include <ios>
- #include <iosfwd>
- #include <iostream>
- #include <istream>
- #include <ostream>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stdexcept>
- #include <streambuf>
- #include <string>
- #include <utility>
- #include <vector>
- #include <cwchar>
- #include <cwctype>
- #include <stack>
- #include <limits.h>
- using namespace std;
- #define MAXN 110
- int i,s,mx,n,cnt,tmp;
- int a[MAXN];
- bool used[MAXN];
- inline bool dfs(int dep,int now,int last)
- {
- int i,fail = 0;
- if (dep> cnt) return true;
- if (now == tmp) return dfs(dep+1,0,1);
- for (i = last; i <= n; i++)
- {
- if (!used[i] && now + a[i] <= tmp && fail != a[i])
- {
- used[i] = true;
- if (dfs(dep,now+a[i],i+1)) return true;
- fail = a[i];
- used[i] = false;
- if (!now) return false;
- }
- }
- return false;
- }
- int main()
- {
- while (scanf("%d",&n) && n)
- {
- s = 0; mx = 0;
- for (i = 1; i <= n; i++)
- {
- scanf("%d",&a[i]);
- s += a[i];
- mx = max(mx,a[i]);
- }
- sort(a+1,a+n+1,greater<int>());
- for (i = mx; i <= s; i++)
- {
- tmp = i;
- if (s % i) continue;
- cnt = s / i;
- memset(used,false,sizeof(used));
- if (dfs(1,0,1)) break;
- }
- printf("%d\n",tmp);
- }
- return 0;
- }
- [POJ 1011] Sticks
来源: http://www.bubuko.com/infodetail-2669555.html