这道题算法题：sticks，我一直是答案错误50%，请问是为什么啊？？？
题目：
poj1011
Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
95 2 1 5 2 1 5 2 141 2 3 40Sample Output
65Hint
题意
给定n根木棒，要求将它们拼成若干根等长的木棒，问拼成的木棒最短长度。
题解：
dfs+剪枝。
将木棒从长到短排序，枚举能拼成的长度搜索，枚举范围是最长木棒的长度到所有木棒总长度中能被总长度整除的部分。
搜索：从最长的木棒开始搜，每搜到一根组合好的木棒变换搜索状态，继续从最长的开始搜，直到用完所有木棒。
剪枝：
1.当某根木棒无法完成组合，则无解，直接结束此次搜索，回溯到上一步；
2.当某个长度的木棒不能再此次搜索中使用，则跳过所有该长度木棒的搜索。
我的代码：
#include
#include
#include
#include
using namespace std;
int visit[70] = { 0 }, sticks[70];
int sum=0,n=0,len;
bool compare(int a, int b)
{
return a>b;
}
int main()
{
bool dfs(int start,int snowlen,int nowlen);
while (cin >> n)
{
if (n == 0)
break;
for (int i = 0; i < n; i++)
{
cin >> sticks;
sum += sticks;
}
sort(sticks, sticks + n, compare);
for (len = sticks[0]; len |
免责声明：本内容仅代表回答会员见解不代表天盟观点，请谨慎对待。
版权声明：作者保留权利，不代表天盟立场。
|
|
|
|
|
|
|
|
天盟APP下载
