DFS(剪枝) POJ 1011 Sticks

时间:2021-07-18 15:57:12

题目传送门

 /*
题意:若干小木棍,是由多条相同长度的长木棍分割而成,问最小的原来长木棍的长度;
DFS剪枝:剪枝搜索的好题!TLE好几次,终于剪枝完全!
剪枝主要在4和5:4 相同长度的木棍不再搜索;5 若新的搜索连第一条都没组合出来,直接break;
详细解释:http://blog.csdn.net/lyy289065406/article/details/6647960
http://www.cnblogs.com/devil-91/archive/2012/08/03/2621787.html
这题虐我千百遍,我待她如。。 656K 0MS 博客随笔第100篇,纪念一下:)
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std; const int MAXN = ;
const int INF = 0x3f3f3f3f;
int a[MAXN];
bool vis[MAXN];
int sum;
int n, cnt; bool cmp(int x, int y)
{
return x > y;
} bool DFS(int len, int ans, int num, int s)
{
if (num == cnt) return true; int pre = -;
for (int i=s; i<=n; ++i)
{
if (vis[i] || a[i] == pre) continue; //Cut 4 vis[i] = true;
if (ans + a[i] < len)
{
if (DFS (len, ans + a[i], num, i) == true) return true;
else pre = a[i];
}
else if (ans + a[i] == len)
{
if (DFS (len, , num+, ) == true) return true;
else pre = a[i];
}
vis[i] = false; if (ans == ) break; //Cut 5
} return false;
} int main(void) //POJ 1011 Sticks
{
//freopen ("POJ_1011.in", "r", stdin); while (scanf ("%d", &n) == && n)
{
sum = ; memset (vis, , sizeof (vis));
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]); sum += a[i];
}
sort (a+, a++n, cmp); //Cut 1 bool flag = false;
for (int i=a[]; i<=sum-i; ++i) //Cut 2
{
if (sum % i == ) //Cut 3
{
cnt = sum / i;
if (DFS (i, , , ) == true)
{
flag = true;
printf ("%d\n", i); break;
}
}
}
if (!flag) printf ("%d\n", sum);
} return ;
} /*
6
5
*/