题意是将一个数字划分为几个数字,使得这几个数字的和尽可能接近一个给定的目标数。如果所有的划分都大于目标数,就输出error,如果有多种划分情况使得和{zd0},则输出rejected。一开始的想法是先考虑划分的个数,比如一个6位数,划分为6个数的话,这6个数的和如果大于目标数则不用再搜索了,因为这肯定是所有划分中和最小的,而最小都比目标数大,自然就没有合要求的答案了。由这个想法就用了迭代加深的回溯算法去做,初始深度就代表划分多少次。结果用了16ms。
但是再想想,其实迭代加深也不一定需要,因为如果多数情况都是有合适划分的话,优先排除的优势就不明显了,而且多了很多重复搜索。对于有{wy}的{zd0}划分或者多个{zd0}划分的情况都是需要搜索所有划分的,因此又写了一个单纯的回溯算法,直接考虑的就是还剩多少位没有划分的问题,因此是以位数为0为终止条件的。
/*
ID: 26723551
PROG: poj 1416 Shredding Company (百练 2803 碎纸机)
LANG: C++
Memory: 256K Time: 16MS
Memory: 256K Time: 0MS
注释部分是迭代加深的回溯算法
直接回溯就可以解决问题了,不用重复搜索,而且是0ms,可以剪枝,当部分和大于目标时不用往下搜索,注意边界条件,无论是搜索的还是输入数据
利用factor数组可以不用额外的数组来存储每位数据,直接int就可以做,比用string方便
*/
#include<iostream>
#include<vector>
using namespace std;
const int factor[7] = {1, 10, 100, 1000, 10000, 100000, 1000000};
//void clip(vector<int> &ary, vector<int> &ans, int &max, bool &flag, int target, int sum, int num, int bit, int depth)
//{
// if(depth == 0){
// if(bit > 0)
// sum += num;
// if(sum <= target){
// if(sum == max){
// flag = false;
// } else if(sum > max){
// flag = true;
// max = sum;
// ans = ary;
// ans.push_back(num);
// }
// }
// } else {
// for(int i = bit - 1; i >= depth; --i){
// if(sum + num / factor[i] <= target){
// ary.push_back(num/factor[i]);
// clip(ary, ans, max, flag, target, sum + num / factor[i], num % factor[i], i, depth-1);
// ary.pop_back();
// }
// }
// }
//}
void dfs(vector<int> &ary, vector<int> &ans, int &max, bool &flag, int target, int sum, int num, int bit)
{
if(bit <= 0){
if(sum == max){
flag = false;
} else if(sum > max){
flag = true;
max = sum;
ans = ary;
}
} else {
for(int i = bit - 1; i >= 0; --i){
if(sum + num / factor[i] <= target){
ary.push_back(num/factor[i]);
dfs(ary, ans, max, flag, target, sum + num / factor[i], num % factor[i], i);
ary.pop_back();
}
}
}
}
int main()
{
int target;
int num;
cin >> target >> num;
while(target != 0 || num != 0){
if(num <= target){
cout << num << ' ' << num << endl;
} else {
int bit = 0;
while(num >= factor[bit])
bit++;
vector<int> ary;
vector<int> ans;
int max = -1;
bool flag = true;
dfs(ary, ans, max, flag, target, 0, num, bit);
//clip(ary, ans, max, flag, target, 0, num, bit, bit - 1);
if(max < 0)
cout << "error" << endl;
else {
/*for(int d = bit - 2; d > 0; --d){
clip(ary, ans, max, flag, target, 0, num, bit, d);
}*/
if(flag){
cout << max;
for(vector<int>::iterator iter = ans.begin(); iter != ans.end(); ++iter)
cout << ' ' << *iter;
cout << endl;
} else
cout << "rejected" << endl;
}
}
cin >> target >> num;
}
return 0;
}