题目链接

题目大意

公司现在要发明一种新的碎纸机，要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值。比如，target的值是50，而纸条上的数字是12346，应该把数字切成四部分，分别是1、2、34、6。因为这样所得到的和 43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。（比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50，而12, 34, 6也不可以，因为它们的和超过50了。碎纸还有以下三个要求：

• 如果target的值等于纸条上的值，则不能切。
• 如果没有办法把纸条上的数字切成小于target，则输出error。如target是1而纸条上的数字是123，则无论你如何切得到的和都比1大。
• 如果有超过一种以上的切法得到最佳值，则输出rejected。如target为15，纸条上的数字是111，则有以下两种切法11、1或者1、11.

你的任务是编写程序对数字进行划分以达到最佳值。

思路分析

设输入的target和待切割的变量如下：

int a;
string b;
while (cin >> a >> b && a)

用DFS搜索所有可能的切割方式，函数如下：

//当前总和sum，前面积累了pre，到了第k个元素
void dfs(int k, int sum, int pre) 

用一个变量pre记录前面累计的值，比如1234，pre=123时表示前三位累积了起来。当遍历完所有位数时，我们对答案进行更新

	if (k == b.size() && sum + pre <= a) {t.push_back(pre);//t存储一直以来切割的数字，res存储答案if (sum + pre > mi)mi = pre + sum, res = t, sign = 1;//越接近a越好else if (sum + pre == mi) sign = 0;t.pop_back();return;}

可以进行一步剪枝，当前累计的值已经超过target就没有继续搜索的必要了

	if (pre + sum > a || k >= b.size())return;

否则，我们对b的第k位数有两种操作方式

• 将其作为单独的一个数，也就是说如果b=12345，pre=123，那么我们将pre存下来，将4单独作为pre传下去。
• 将其和前面传入的pre进行拼凑，即拼成1234传下去。

	t.push_back(pre);dfs(k + 1, sum + pre, b[k] - '0');//单独作为一个元素t.pop_back();//作为高位传下去dfs(k + 1, sum, pre * 10 + b[k] - '0');//与前面结合成为一个高位

完整代码：

//208K	0MS
#define inf 0x3f3f3f3f
#define vec vector<int>
#define ll long long
#define P pair<int,int>
#define MAX 10005int a, sign, mi;
vec res, t;
string b;//当前总和sum，前面积累了pre，到了第k个元素
void dfs(int k, int sum, int pre) {if (k == b.size() && sum + pre <= a) {t.push_back(pre);if (sum + pre > mi)mi = pre + sum, res = t, sign = 1;//越接近a越好else if (sum + pre == mi) sign = 0;t.pop_back();return;}if (pre + sum > a || k >= b.size())return;t.push_back(pre);dfs(k + 1, sum + pre, b[k] - '0');//单独作为一个元素t.pop_back();//作为高位传下去dfs(k + 1, sum, pre * 10 + b[k] - '0');//与前面结合成为一个高位
}int main() {while (cin >> a >> b && a) {sign = 1; mi = 0; t.clear(); res.clear();dfs(1, 0, b[0] - '0');if (res.size() == 0)printf("error\n");else if (sign == 0)printf("rejected\n");else {printf("%d", mi);for (int i = 0; i < res.size(); i++)printf(" %d", res[i]);printf("\n");}}
}