题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5009
题目意思：给出两个mass：x 和 y，问如何将其中一个 mass 一分为二（当然分完之后它们的和要等于原来的mass，或x 或 y），使得利用这三个mass 可称的数量最大。输出这个最大数量。
网上参考别人用STL中的set来写，太厉害了！！！考虑到set对于重复的元素只存储一个，那么当三个mass组合的过程中有重复的，它都会自动舍弃有重复的，不需要用if来判断！另外，也有可能其中两个mass是相等的，这时如果各放一边，就只会称到0，即不能称到任何物体！所以预先把0插入，这就是代码中为什么最后要返回 st.size()-1 的原因！！
方法一：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <set> 6 using namespace std; 7 8 set<int> st; 9 int cal(int a, int b, int c) 10 { 11 st.clear(); // 每一次都要清空集合里的元素 12 st.insert(0); // 考虑到左右两边各有一个相同mass的情况，这时称不了物体！ 13 st.insert(a); // 只选一个mass称物体 14 st.insert(b); 15 st.insert(c); 16 17 st.insert(a+b); // 只选两个mass称另外一边的物体 18 st.insert(abs(a-b)); 19 st.insert(b+c); 20 st.insert(abs(b-c)); 21 st.insert(a+c); 22 st.insert(abs(a-c)); 23 24 st.insert(abs(a+b-c)); // 两个mass在一边，另一边放第三个mass和代称物 25 st.insert(abs(a+c-b)); 26 st.insert(abs(b+c-a)); 27 28 st.insert(a+b+c); // 三个mass在一边，另一边称物体 29 return st.size()-1; 30 } 31 32 int main() 33 { 34 int T, x, y, sum; 35 while (scanf("%d", &T) != EOF) 36 { 37 while (T--) 38 { 39 sum = 0; 40 scanf("%d%d", &x, &y); 41 for (int i = 1; i <= x; i++) 42 { 43 int t1 = i; 44 int t2 = x-i; 45 int t3 = y; 46 sum = max(sum, cal(t1, t2, t3)); 47 } 48 for (int i = 1; i <= y; i++) 49 { 50 int t1 = i; 51 int t2 = y-i; 52 int t3 = x; 53 sum = max(sum, cal(t1, t2, t3)); 54 } 55 printf("%d ", sum); 56 } 57 } 58 return 0; 59 }
方法二：用到dfs
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 int cnt, num[3]; 8 int vis[300]; 9 10 void dfs(int count, int now) 11 { 12 if (!vis[now] && now > 0) 13 { 14 vis[now] = 1; 15 cnt++; 16 } 17 if (count == 3) 18 return; 19 dfs(count+1, now+num[count]); 20 dfs(count+1, now-num[count]); 21 dfs(count+1, now); 22 } 23 24 int main() 25 { 26 int T, x, y, sum; 27 while (scanf("%d", &T) != EOF) 28 { 29 while (T--) 30 { 31 sum = 0; 32 scanf("%d%d", &x, &y); 33 for (int i = 1; i <= x; i++) 34 { 35 cnt = 0; 36 memset(vis, 0, sizeof(vis)); 37 num[0] = i; 38 num[1] = x-i; 39 num[2] = y; 40 dfs(0, 0); 41 sum = max(sum, cnt); 42 } 43 for (int i = 1; i <= y; i++) 44 { 45 cnt = 0; 46 memset(vis, 0, sizeof(vis)); 47 num[0] = i; 48 num[1] = y-i; 49 num[2] = x; 50 dfs(0, 0); 51 sum = max(sum, cnt); 52 } 53 printf("%d ", sum); 54 } 55 } 56 return 0; 57 }