首页 > 代码库 > hdu 1258 Sum It Up(dfs+去重)
hdu 1258 Sum It Up(dfs+去重)
题目大意:
给你一个总和(total)和一列(list)整数,共n个整数,要求用这些整数相加,使相加的结果等于total,找出所有不相同的拼凑方法。
例如,total = 4,n = 6,list = [4,3,2,2,1,1]。
有四种不同的方法使得它们相加的结果等于total(即等于4),分别为:4,3+1,2+2, 2+1+1。
在同一种拼凑方式中,每个数字不能被重复使用,但是在list中可能存在许多相等的数字。
输入:
输入包含许多测试用例,每个用例仅占一行。每个用例包含t(total),接下来是n,接着是用空格隔开的n个整数。如果n等于零,表示输入结束。t∈(0,1000),n∈[1, 12],list中的每个整数∈[1, 100],list中的数字是以降序排列,数字中可能出现重复的数字。
输出:
每个测试用例,第一行输出“Sums of [total的值]:”,接下每一行输出一个结果集,如果一个结果集都没有则输出“NONE”。每个结果集要按照降序输出,并且结果集之间也要按照降序排序,结果集之间的比较从第一个数字开始,数字大的结果集大,如果第一个数字相同,则比较第二个数字,第二个数字大的,则结果集大,如果第二个数字也相同,则比较第三个数字,以此类推。不能出现相同的结果集。
解题思路:
类似hdu 1455 Sticks,但是比1455简单的多。搞一个数组记录结果集,每次搜索到结果的时候,就输出结果集,由于list是降序的,并且数字可能在list中重复出现,因此回溯的时候记得去掉重复的结果集。
AC代码:
1 //19475530 2017-01-02 21:07:46 Accepted 1258 0MS 1720K 1332 B C++ 潮州牛肉丸 2 #include <stdio.h> 3 #include <string.h> 4 5 int total; // the list that add up to total. t < 1000 6 int n; // list中元素个数 7 int list[20]; // 记录数字 list[x] ∈ (0, 100) 8 bool visit[20]; // 判重 9 10 int result[1010]; // 记录结果集 11 int count; // 记录result中的元素个数 12 int flag; // 记录是否搜索到结果,一次都没有搜索到则为false 13 14 void init(void) 15 { 16 count = 0; 17 flag = false; 18 memset(list, 0x00, sizeof(list)); 19 memset(visit, 0x00, sizeof(visit)); 20 } 21 22 // sum:当前累加和,index:上一次搜索到的下标位置 23 void dfs(int sum, int index) 24 { 25 if (total == sum) 26 { 27 // 输出结果集 28 flag = true; 29 printf("%d", result[0]); 30 for (int i = 1; i < count; ++i) 31 printf("+%d", result[i]); 32 printf("\n"); 33 return; 34 } 35 36 for (int i = index + 1; i < n; ++i) 37 { 38 if (true == visit[i]) 39 continue; 40 41 if (list[i] + sum <= total) 42 { 43 result[count++] = list[i]; 44 visit[i] = true; 45 dfs(list[i] + sum, i); 46 visit[i] = false; 47 count--; 48 49 // 关键:去掉重复的结果集 50 while (i < n && list[i] == list[i + 1]) ++i; 51 } 52 } 53 return; 54 } 55 56 int main(void) 57 { 58 while (scanf("%d %d", &total, &n) != EOF && 0 != n) 59 { 60 init(); 61 for (int i = 0; i < n; ++i) 62 scanf("%d", &list[i]); 63 64 printf("Sums of %d:\n", total); 65 dfs(0, -1); 66 if (false == flag) 67 printf("NONE\n"); 68 } 69 return 0; 70 }
hdu 1258 Sum It Up(dfs+去重)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。