http://poj.org/problem?id=1011
题意：若干个相同长度的棍子被剪成若干长度的小棍，求每根棍子原来的可能最小长度。
思路：很经典的搜索题。
我一开始各种超时，这题需要很多剪枝。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std; int n;
int a[];
int vis[]; bool cmp(int a, int b)
{
return a > b;
} int dfs(int len, int left_len, int number) //棍子长度、还需要匹配长度、未匹配棍子数量
{
if (left_len == && number == ) return len; //所有棍子已全部匹配完毕
if (left_len == ) //已匹配完一根棍子
left_len = len;
for (int i = ; i < n; i++)
{
if (!vis[i] && a[i] <= left_len)
{
vis[i] = ;
if (dfs(len, left_len - a[i], number - )) //深搜
return len;
vis[i] = ;
if (left_len == a[i] || len == left_len) break; //剪枝，没有数可以和当前值匹配，直接跳出循环
while (a[i] == a[i + ]) i++; //剪枝，如果后面和前面一样，则跳过
}
}
return ;
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
while (cin >> n && n)
{
memset(vis, , sizeof(vis));
int sum = ;
int maxn = ;
for (int i = ; i < n; i++)
{
cin >> a[i];
sum += a[i];
//if (a[i]> maxn) maxn = a[i]; //记录长棍子，dfs时从最长棍子开始
}
int k = ;
sort(a, a + n,cmp);
for (int i = a[]; i <= sum; i++)
{
if (sum%i == ) //剪枝，不能除尽说明棍子长度不能为i
{
k = dfs(i, , n);
if (k) break;
}
}
cout << k << endl;
}
return ;
}