首页 > 代码库 > hdu 1258 Sum It Up
hdu 1258 Sum It Up
Sum It Up
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1258
题目的意思:给一个sum的值,给一个n,接下来有n个数
这几个数随机组合等于sum时,输出怎么样组合的。
注意:不能有重复的
解题思路:用DFS深搜,这个我写的时候都把自己搞晕了,看了别人的思路才憋出来,屡思路就屡了半天,还是去重的地方理解不深,还是太水啊
Sample Input
4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0
Sample Output
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<queue> 6 #include<cmath> 7 #include<algorithm> 8 using namespace std; 9 int sum,n,flag;10 int a[15],b[15],vis[15];11 bool cmp(int a,int b)12 {13 return a>b;14 }15 void dfs(int x,int y,int z)16 {17 int i,j=0;18 if(y>sum)19 return ;20 if(y==sum)21 {22 flag=0;23 for(i=0;i<x;i++)24 {25 if(i==0)26 printf("%d",b[i]);27 else28 printf("+%d",b[i]);29 }30 printf("\n");31 return ;32 }33 for(i=z;i<n;i++)34 {35 if(!vis[i])36 {37 vis[i]=1;38 b[x]=a[i];39 dfs(x+1,y+a[i],i+1);40 vis[i]=0;41 while(a[i]==a[i+1])//去重42 i++;43 }44 }45 }46 47 48 int main()49 {50 int i;51 while(~scanf("%d%d",&sum,&n))52 {53 memset(vis,0,sizeof(vis));54 if(!sum&&!n)55 break;56 for(i=0;i<n;i++)57 scanf("%d",&a[i]);58 sort(a,a+n,cmp);59 flag=1;60 printf("Sums of %d:\n",sum);61 dfs(0,0,0);62 if(flag)63 {64 printf("NONE\n");65 }66 }67 return 0;68 }
hdu 1258 Sum It Up
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。