Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 57061 Accepted: 12462
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 1
4
1 2 3 4
0
Sample Output
65
/**
Input:
64
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
0
Output:
1251
**/
剪枝：
降序排序，每轮验证只要成功就进行下一轮，只要失败就认为不能分成I组。
1、每轮验证只要成功就进行下一轮。
因为我们是降序排序的，所以在搜索的时候总是先搜索到大的。
例如：当前（sum mod i=10），我们进行第一次验证的时候搜索出了5+3+2=10.
那么第一次验证就可以宣告结束了。因为，再搜索出来的肯定是比当前序列中某一个木棍短的，
比如，（2+3）+3+2=10， 这种结果是不优的，因为同样的长度，用长木棍去填补，要比用多个短木棍去填补所留给下一轮的机会多。
基于这个原理，我们得到的结论就是，对于每轮验证只要搜到一个解就进行下一轮。
2、只要任意一轮验证失败就认为不能分成I组。
还是根据我们刚才的原理，假设在第三轮时的验证失败了，那么绝没有回溯到第二轮或第一轮更改决策的必要，因为前面作出的决策已经是最优的了，更改决策只会让它们用更多的比原决策小的木棍，显而易见，这是不优的。
// author: jfo()
////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int LEN;
bool check(vector<int> v, int len);
bool fn(vector<int>& v, int len, int up_bound)
{
if(0 == len) {
if(v.empty())
return true;
else
return check(v, LEN);
}
for(int i = up_bound; i >= 0; i–) {
if(v[i] > len)
continue;
vector<int> tmp(v);
int val = v[i];
v.erase(v.begin() + i);
if(fn(v, len - val, i - 1)) {
return true;
}
v = tmp;
while(i > 0 && v[i-1] == val)
i–;
}
return false;
}
bool check(vector<int> v, int len)
{
int m = v.back();
v.pop_back();
return fn(v, len - m, v.size() - 1);
}
int main()
{
int n;
int i;
while(cin >> n && n) {
int d;
int sum = 0;
vector<int> parts;
for(i = 0; i < n; i++) {
cin >> d;
parts.push_back(d);
sum += d;
}
make_heap(parts.begin(), parts.end());
int count = sum / parts.front();
sort_heap(parts.begin(), parts.end());
for(i = count; i > 0; i–) {
if(sum % i) continue;
LEN = sum / i;
if(check(parts, LEN)) {
cout << LEN << endl;
break;
}
}
}
return 0;
}
下面这个测试下面用例时有点问题，输出为2502
64
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
0
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int LEN;
vector<int> parts;
int selected[64];
bool check(int len, int segments)
{
if (len < 0 || len > 64 50)
return false;
if (len == LEN && segments == 0)
return true;
bool flag = false;
int i = N - 1;
while (i >= 0 && (selected[i] || parts[i] > len))
i–;
if (i < 0)
return false;
selected[i] = 1;
if (len - parts[i] == 0)
flag = check(LEN, segments - 1);
else
flag = check(len - parts[i], segments);
if (flag)
return true;
else
selected[i] = 0;
return false;
}
int main()
{
int i, k;
while(cin >> N) {
if (0 == N)
return 0;
int sum = 0;
parts.clear();
for (i=0; i<N; i++) {
cin >> k;
parts.push_back(k);
selected[i] = 0;
sum += k;
}
sort(parts.begin(), parts.end());
LEN = parts.rbegin() - 1;
while (++LEN <= sum) {
if (sum % LEN)
continue;
if (check(LEN, sum / LEN)) {
cout << LEN << endl;
break;
}
}
if (LEN > sum)
cout << "NONE" << endl;
}
return 0;
}