OpenJudge 2803 碎纸机 / Poj 1416 Shredding Company

1.链接地址：

http://poj.org/problem?id=1416

http://bailian.openjudge.cn/practice/2803

2.题目：

总时间限制:

1000ms

内存限制:

65536kB

描述

你现在负责设计一种新式的碎纸机。一般的碎纸机会把纸切成小片，变得难以阅读。而你设计的新式的碎纸机有以下的特点：

1.每次切割之前，先要给定碎纸机一个目标数，而且在每张被送入碎纸机的纸片上也需要包含一个数。
2.碎纸机切出的每个纸片上都包括一个数。
3.要求切出的每个纸片上的数的和要不大于目标数而且与目标数最接近。

举 一个例子，如下图，假设目标数是50，输入纸片上的数是12346。碎纸机会把纸片切成4块，分别包含1，2，34和6。这样这些数的和是43 (= 1 + 2 + 34 + 6)，这是所有的分割方式中，不超过50，而又最接近50的分割方式。又比如，分割成1，23，4和6是不正确的，因为这样的总和是34 (= 1 + 23 + 4 + 6)，比刚才得到的结果43小。分割成12，34和6也是不正确的，因为这时的总和是52 (= 12 + 34 + 6)，超过了50。

还有三个特别的规则：
1.如果目标数和输入纸片上的数相同，那么纸片不进行切割。
2.如果不论怎样切割，分割得到的纸片上数的和都大于目标数，那么打印机显示错误信息。
3.如果有多种不同的切割方式可以得到相同的最优结果。那么打印机显示拒绝服务信息。比如，如果目标数是15，输入纸片上的数是111，那么有两种不同的方式可以得到最优解，分别是切割成1和11或者切割成11和1，在这种情况下，打印机会显示拒绝服务信息。


为了设计这样的一个碎纸机，你需要先写一个简单的程序模拟这个打印机的工作。给定两个数，第一个是目标数，第二个是输入纸片上的数，你需要给出碎纸机对纸片的分割方式。

输入

输入包括多组数据，每一组包括一行。每行上包括两个正整数，分别表示目标数和输入纸片上的数。已知输入保证：两个数都不会以0开头，而且两个数至多都只包含6个数字。

输入的最后一行包括两个0，这行表示输入的结束。

输出

对每一组输入数据，输出相应的输出。有三种不同的输出结果：

sum part1 part2 ...
rejected
error

第一种结果表示：
1.每一个partj是切割得到的纸片上的一个数。partj的顺序和输入纸片上原始数中数字出现的次序一致。
2.sum是切割得到的纸片上的数的和，也就是说：sum = part1 + part2 +...
第一种结果中相邻的两个数之间用一个空格隔开。

如果不论怎样切割，分割得到的纸片上数的和都大于目标数，那么打印“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

来源

翻译自Japan 2002 Kanazawa的试题

3.思路：

dfs(深度优先搜索)+剪枝

4.代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <string>
  4 #include <vector>
  5 #include <cstdlib>
  6 
  7 using namespace std;
  8 
  9 int max_sum;
 10 
 11 int res_sum;
 12 vector<int> res_path;
 13 int count;
 14 
 15 int sum;
 16 vector<int> path;
 17 
 18 
 19 void dfs(string str)
 20 {
 21     //for(int v_i = 0; v_i < path.size(); ++v_i) cout << path[v_i] << " "; cout << "(" << str << ")(" << sum << ")";cout << endl;
 22     if(str.size() == 0)
 23     {
 24         
 25         if(sum <= max_sum && sum == res_sum)
 26         {
 27             ++count;
 28             //res_path.clear();
 29             //for(int v_i = 0; v_i < path.size(); ++v_i) res_path.push_back(path[v_i]);
 30             //for(int v_i = 0; v_i < path.size(); ++v_i) cout << path[v_i] << " "; cout << "(" << str << ")(" << sum << ")";cout << endl;
 31             res_path = path;
 32         }
 33         else if(sum <= max_sum && sum > res_sum)
 34         {
 35             res_sum = sum;
 36             count = 1;
 37             //for(int v_i = 0; v_i < path.size(); ++v_i) cout << path[v_i] << " "; cout << "(" << str << ")(" << sum << ")";cout << endl;
 38             res_path = path;
 39             //res_path.clear();
 40             //for(int v_i = 0; v_i < path.size(); ++v_i) res_path.push_back(path[v_i]);
 41         }
 42         return;
 43     }
 44 
 45     for(int i = str.size() - 1; i >= 0; --i)
 46     {
 47         string str_left = str.substr(0,i);
 48         string str_right = str.substr(i);
 49 
 50         int left = atoi(str_left.c_str());
 51         int right = atoi(str_right.c_str());
 52 
 53         //剪枝
 54         if(sum + right > max_sum) continue;
 55 
 56         //剪枝二
 57         if(res_sum == max_sum && count > 1) break;
 58 
 59         sum += right;
 60         path.push_back(right);
 61 
 62         dfs(str_left);
 63 
 64         sum -= right;
 65         path.pop_back();
 66     }
 67 
 68     return;
 69 }
 70 
 71 int main()
 72 {
 73     //freopen("C://input.txt","r",stdin);
 74 
 75     string str;
 76     cin >> max_sum >> str;
 77 
 78     while(max_sum != 0 || str.size() != 1 || str[0] != '0')
 79     {
 80         int num = atoi(str.c_str());
 81         if(num <= max_sum)
 82         {
 83             cout << num << " " << num << endl;
 84         }
 85         else
 86         {
 87             sum = 0;
 88             path.clear();
 89 
 90             res_sum = -1;
 91 
 92             dfs(str);
 93 
 94             if(res_sum == -1) cout << "error" << endl;
 95             else if(count > 1) cout << "rejected" << endl;
 96             else
 97             {
 98                 cout << res_sum;
 99                 for(int i = res_path.size() - 1; i >= 0; --i) cout << " " << res_path[i];
100                 cout << endl;
101             }
102         }
103 
104 
105 
106         cin >> max_sum >> str;
107     }
108 
109     return 0;
110 }