POJ1416 Shredding Company(dfs)

 题目链接。

分析：

这题从早上调到现在。也不算太麻烦，细节吧。

每个数字都只有两种状态，加入前一序列和不加入前一序列。DFS枚举。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <string>
#include <queue>

using namespace std;

int ord[10], len, ans_a[10], tar, max_ans, cnt;
char s[10];
bool flag;

void dfs(int cur_s, int cur_t, int cur) {
    if(cur_s+cur_t > tar) {        // error
        return ;
    }
    else if(cur == len) {    //
        int t = cur_s + cur_t;
        if(t > tar) return ;
        else if(t > max_ans) {
            cnt = 1;
            max_ans = t;
            memcpy(ans_a, ord, sizeof(ord));
        }
        else if(t == max_ans) {
            cnt++;
        }
        flag = true;
        return ;
    }
   
    ord[cur] = 1;
    dfs(cur_s+cur_t+s[cur]-'0', 0, cur+1);

    if(cur != len-1) {
        ord[cur] = 0;
        dfs(cur_s, (cur_t+s[cur]-'0')*10, cur+1);
    }
}


int main() {
    int n;
  //  freopen("my.txt", "r", stdin);

    while(scanf("%d %d", &tar, &n) == 2 && (n | tar)) {
        flag = false;
        max_ans = 0; cnt = 0;

        sprintf(s, "%d", n);
        len = strlen(s);

        dfs(0, 0, 0);

        if(!flag) printf("error
");
        else if(cnt >= 2) printf("rejected
");
        else {
            printf("%d", max_ans);
            int sn=0;
            for(int i=0; i<len; i++) {
                if(ans_a[i] == 1) {
                    printf(" %d", sn*10+s[i]-'0');
                    sn = 0;
                }
                else {
                    sn = sn*10+s[i]-'0';
                }
            }

            putchar('
');
        }
    }

    return 0;
}