POJ1416 (dfs)
公司现在要发明一种新的碎纸机，要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值（可以选择不切割）。比如，target的值是50，而纸条上的数字是12346，应该把数字切成四部分，分别是1、2、34、6。因为这样所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。（比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50，而12, 34, 6也不可以，因为它们的和超过50了。要求（如果全部超过目标数字，输出error，如果有两种及以上和一样的最小答案，输出rejected）
示例输入
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
示例输出
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected
思路：切割数字的过程就是一个简单的排列组合隔板法问题，使用dfs找到各个组合，验证各个组合的和即可，判断方法是，满足条件且不与已有最小答案相等为1，满足条件但；与最小答案相等为2；没有满足条件的为0；
answer：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int pap[6];
int t, n, p;
bool flag[6];
bool cpy[6];
int ans,record;
void check(){
int sum = 0, temp = 0;
for(int i = 0;i <= p;i++){
if(flag[i] || i == p){
sum += temp;
temp = 0;
}
temp = temp * 10 + pap[i];
}
if(sum > ans && sum <= t) {
record = 1;
ans = sum;
memcpy(cpy,flag,sizeof(flag));
}
else if(sum == ans) record = 2;
}
void dfs(int deep,int pre){
if(deep == n) {
check();
return;
}
for(int i = pre + 1;i < p;i++){
if(!flag[i]) {
flag[i] = true;
dfs(deep + 1, i);
flag[i] = false;
}
}
}
int main() {
char ch;
while(1){
scanf("%d", &t);
if(t == 0) break;
p = 0;
ans = -1;
record = 0;
while((ch = getchar()) != '\n') {
if(ch >= '0' && ch <= '9') {
pap[p] = ch - '0';
p++;
}
}
memset(flag, false, sizeof(flag));
for(n = 0;n < p;n++){
dfs(0,0);
}
if(record == 0) printf("error\n");
else if(record == 2) printf("rejected\n");
else {
printf("%d", ans);
int temp = 0;
for(int i = 0;i <= p;i++){
if(cpy[i] || i == p){
printf(" %d",temp);
temp = 0;
}
temp = temp * 10 + pap[i];
}
printf("\n");
}
}
return 0;
}