ZOJ1101的强化版,求序列中多个数之和是否存在于序列之中,并排序输出.
由于题目要求按算式"字符串"顺序输出,在DFS过程中以数字个数为DFS的深度限制.
Code
1
#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6vector<int> datas;
7vector<int> result;
8bool isFind;
9
10// int sort function
11int IntCompare(const void * i1, const void * i2)
12
{
13
return (*(const int*)i1) > (*(const int*)i2);
14
}
15
16// start is the search start index
17// dest_deep is the search destination depth
18// current_deep is the search of current depth
19// current_sum is the sum of current searchable numbers
20void DFS(int start, int dest_deep, int current_deep, int current_sum)
21{
22 // if reach the dstination depth
23 if(current_deep == dest_deep)
24
{
25 // if we have the sum in the list
26 if(binary_search(datas.begin(), datas.end(), current_sum))
27 {
28 // output it
29 for(int i = 0; i < dest_deep - 1; ++i)
30 {
31 cout << result[i] << "+";
32
}
33 cout << result[dest_deep - 1] << "=" << current_sum << endl;
34 isFind = true;
35 }
36 }
37 // otherwise if we haven't reach the destination depth, go on searching
38 else
39 {
40 int size = datas.size();
41 // search from start to avoid duplicate result such as 1+2=3 and 2+1=3
42 for(int i = start; i < size; ++i)
43 {
44 // store my search result
45 if(current_deep < result.size())
46 {
47 result[current_deep] = datas[i];
48 }
49 else
50 {
51 result.push_back(datas[i]);
52 }
53
54 // if the sum is bigger than the biggest one in the list, break the loop
55 if(current_sum + datas[i] > datas[datas.size() - 1])
56 break;
57 // search next, increase start avoid duplicate, increase depth, re-calculate sum
58 DFS(i + 1, dest_deep, current_deep + 1, current_sum + datas[i]);
59 }
60 }
61}
62
63int _tmain(int argc, _TCHAR* argv[])
64{
65 int n;
66 cin >> n;
67 for(int i = 0; i < n; ++i)
68 {
69 int count;
70 cin >> count;
71 int number;
72 for(int j = 0; j < count; ++j)
73 {
74 cin >> number;
75 datas.push_back(number);
76 }
77
78 qsort(&datas[0], count, sizeof(int), IntCompare);
79
80 isFind = false;
81 for(int i = 2; i < count; ++i)
82 {
83 // i indicate the depth of the search, 2 is the lowest and count-1 is the largest
84 DFS(0, i, 0, 0);
85 }
86 if(!isFind)
87 cout << "Can't find any equations." << endl;
88 cout << endl;
89 datas.clear();
90 }
91 return 0;
92}
93posted on 2009-03-31 20:54
肖羽思 阅读(2134)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ