问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1416思路:
深度优先搜索，找出所有可能的划分，并适当减枝
这里搜索的对象是什么？
我的第一个想法受到了前几天完成PKU 1950的启发，对于从高到低的每一位，有两种可能:
a. 作为解的一部分，加入总和
b. 不加入总和，而是作为向下继续搜索时的高位
dfs(depth, cur_sum, pre)
depth: 搜索深度
cur_sum: 当前总和
pre: 保留位
经过一段时间的调试，一次AC了
存在的问题是: 对于每一种可能的解都会重复记录两次，例如:
输入 376 144139
输出 283 144 139
dfs(6, 283, 0)与dfs(6, 144, 139)都可以得到该解
之后，查看了网上的代码，原来不用想的这么复杂
对于第k位，我们搜索从其开始的所有可能，然后递归，例如:
对于将被“粉碎"的12346，对于第一位'1'，可能的划分有1, 12, 123, 1234, 12346
代码(方法一):
1 #define MAX_LEN 7
2 int target, num;
3 int digits_count, digits[MAX_LEN];
4 int sum_count, sum, parts_count, parts[MAX_LEN];
5 int ans_count, ans[MAX_LEN];
6
7 void
8 init()
9 {
10 int i, temp, rem;
11 memset(digits, -1, sizeof(digits));
12 memset(parts, -1, sizeof(parts));
13 digits_count = sum_count = parts_count = 0;
14 sum = -1;
15 rem = num;
16 do {
17 digits[digits_count++] = rem % 10;
18 rem /= 10;
19 } while(rem!=0);
20 for(i=0; i<digits_count/2; i++) {
21 temp = digits[i];
22 digits[i] = digits[digits_count-i-1];
23 digits[digits_count-i-1] = temp;
24 }
25 }
26
27 void
28 dfs(depth, cur_sum, pre)
29 {
30 if(cur_sum+pre>target) /* pruning */
31 return;
32 //printf("dfs(%d, %d, %d)\n", depth, cur_sum, pre);
33 if(depth == digits_count) {
34 if(pre != 0) {
35 parts[parts_count++] = pre;
36 cur_sum += pre;
37 }
38 if(cur_sum == sum)
39 ++sum_count;
40 if(cur_sum > sum) {
41 sum = cur_sum;
42 sum_count = 1;
43 ans_count = parts_count;
44 memcpy(ans, parts, sizeof(int)*ans_count);
45 }
46 if(pre != 0)
47 parts[parts_count--] = -1;
48 return;
49 }
50 /* branch 1 */
51 parts[parts_count++] = digits[depth] + pre * 10;
52 dfs(depth+1, cur_sum+parts[parts_count-1], 0);
53 parts[parts_count--] = -1;
54 /* branch 2 */
55 dfs(depth+1, cur_sum, pre*10+digits[depth]);
56 }
代码(方法二):
1 #define MAX_LEN 7
2 int target, len;
3 char num[MAX_LEN];
4 int sum_count, sum, parts_count, parts[MAX_LEN];
5 int ans_count, ans[MAX_LEN];
6
7 void
8 dfs(int depth, int cur_sum)
9 {
10 int i, value = 0;
11 if(cur_sum > target) /* pruning */
12 return;
13 if(depth == len) {
14 if(cur_sum == sum)
15 ++sum_count;
16 if(cur_sum > sum) {
17 sum = cur_sum;
18 sum_count = 1;
19 ans_count = parts_count;
20 memcpy(ans, parts, sizeof(int)*ans_count);
21 }
22 return;
23 }
24 for(i=depth; i<len; i++) {
25 value *= 10;
26 value += (num[i]-'0');
27 parts[parts_count++] = value;
28 dfs(i+1, cur_sum+value);
29 parts[parts_count--] = -1;
30 }
31 }