题意：

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

1、如果$target$的值等于纸条上的值，则不能切。 2、如果没有办法把纸条上的数字切成小于$target$，则输出$error$。如$target$是$1$而纸条上的数字是$123$，则无论你如何切得到的和都比$1$大。 3、如果有超过一种以上的切法得到最佳值，则输出$rejected$。如$target$为$15$，纸条上的数字是$111$，则有以下两种切法$11$、$1$或者$1$、$11$。 你的任务是编写程序对数字进行划分以达到最佳值。

解题思路：

$DFS$

$(1)$比如一个$6$位数$n$，切成为$6$个数的话，这$6$个数的和如果大于目标数$target$则不用再搜索了，因为这肯定是所有划分中和最小的，而最小都比目标数大，自然就没有合要求的答案了。 $(2)$ 如何切分，假如以$50$ $12346$ 为例。 第一步，先切下一个"$1$"，然后递归去切"$2346$"； 第二步，再切下一个"$12$"，然后递归去切"$346$"； 第三步，再切下一个"$123$"，然后递归去切"$46$"； 第四步，再切下一个"$1234$" 然后递归去切"$6$" 第五步，再切下"$12346$"。

$(3)$切下来的 前面的数字串部分 则加入到划分的和，剩下的部分继续递归，直到已经划分出来的数字长度$len$等于数字串总长度$strlen(num)$。为了记录划分方式，使用$int$数组$devide$记录每一次划分的长度，比如样例$50$ $12346$划分为$43$ $1$ $2$ $34$ $6$，那$devide[0] = 1$,$devide[1] = 1$,$devide[2] = 2$,$devide[3] = 1$。而且为了保存最优解，需要在已经划分出来的数字长度$len$等于数字串总长度$strlen(num)$，并且$abs(bestx-target)>abs(sum-target)$时，更新最优解$bestx = sum$，并且将$devide$转存到$ansdevide$中，为了方便之后答案的输出。

$(4)$使用字符数组存储数字串$num$，这样在搜索时，只要控制字符数组的起止位置就可以模拟数字串的拆分。

$(5)$剪枝方法：在搜索时若发现部分和 大于（不能等于）$target$时，则可结束搜索。

在进入$dfs$搜索时，可以把特殊情况排除

1）$error$的判定要在搜索前进行

2）当数字串$num$和$target$相等时，直接输出，不用划分

3）当数字串的每一位数字之和$sum2$等于$target$时，直接逐位输出，每个数字为一个划分

注意这种情况有一个特例，就是$0$出现的时候，

例如样例：$6$ $1104$

它的最优划分有两种 $6$ $1$ $1$ $0$ $4$

$6$ $1$ $1$ $04$

所以此样例应该输出$rejected$

所以这种情况下，应该保证数字串$num$中没有$0$，才可以直接逐位输出

$(6)rejected$（多个最优解）的判定要在搜索后判定。当最优解出现两次的时候（出现$abs(bestx-target)==abs(sum-target)$），使用全局变量$Count$计数。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int target;
char num[10];
int bestx;
int Count;
int anslen;
int ansdevide[10];
void dfs(char *ch,int len,int sum,int c,int *devide)
{///len为当前已经划分的数字串的长度，sum为当前已划分的数字的总和
///c为划分的数字的块数
    if(len == strlen(num))
    {
        if(abs(bestx-target)>abs(sum-target))
        {
            Count=0;
            anslen = c;
            bestx = sum;
            for(int i=0;i<c;i++)
                ansdevide[i] = devide[i];
            return;
        }
        if(abs(bestx-target)==abs(sum-target))///出现多个最优解
        {
            Count++;
        }
        return;
    }
    for(int i=1;i<=strlen(ch);i++)
    {///确定下一步划分的长度i
        int newsum = 0;
        for(int j=0;j<i;j++)
            newsum = newsum*10 + (ch[j]-'0');
        newsum+=sum;
        devide[c] = i;
        if(newsum<=target)
            dfs(ch+i,len+i,newsum,c+1,devide);
    }
}

int main()
{
    while(cin>>target && target)
    {
        cin>>num;
        int sum1 = 0;///计算纸上的数是多少
        int sum2 = 0;///每一位的和
        for(int i=0;i<strlen(num);i++)
        {
            sum1 = sum1*10+(num[i]-'0');
            sum2 += num[i]-'0';
        }
        if(sum1 == target)
            cout<<target<<" "<<target<<endl;
        else if(sum2 > target)
        {
            cout<<"error"<<endl;
        }
        else if(sum2 == target && !strchr(num,'0'))
        {
            cout<<target;
            for(int i=0;i<strlen(num);i++)
            {
                cout<<" "<<num[i];
            }
            cout<<endl;
        }else
        {
            Count = 0;
            bestx = 0;
            int devide[10];
            dfs(num,0,0,0,devide);
            if(Count > 0)
                cout<<"rejected"<<endl;
            else{
                cout<<bestx;
                int temp=0;
                for(int i=0;i<anslen;i++)
                {
                    cout<<" ";
                    for(int j=temp;j<temp+ansdevide[i];j++)
                    {
                        cout<<num[j];
                    }
                    temp += ansdevide[i];
                }
                cout<<endl;
            }
        }

    }
    return 0;
}