問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1416思路:
深度優(yōu)先搜索，找出所有可能的劃分，并適當(dāng)減枝
這里搜索的對(duì)象是什么？
我的第一個(gè)想法受到了前幾天完成PKU 1950的啟發(fā)，對(duì)于從高到低的每一位，有兩種可能:
a. 作為解的一部分，加入總和
b. 不加入總和，而是作為向下繼續(xù)搜索時(shí)的高位
dfs(depth, cur_sum, pre)
depth: 搜索深度
cur_sum: 當(dāng)前總和
pre: 保留位
經(jīng)過一段時(shí)間的調(diào)試，一次AC了
存在的問題是: 對(duì)于每一種可能的解都會(huì)重復(fù)記錄兩次，例如:
輸入 376 144139
輸出 283 144 139
dfs(6, 283, 0)與dfs(6, 144, 139)都可以得到該解
之后，查看了網(wǎng)上的代碼，原來不用想的這么復(fù)雜
對(duì)于第k位，我們搜索從其開始的所有可能，然后遞歸，例如:
對(duì)于將被“粉碎"的12346，對(duì)于第一位'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 }