首页 > 代码库 > hdu 1258 Sum It Up

hdu 1258 Sum It Up

2024-08-04 21:27:24   219人阅读

　　

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 }
View Code

 

 
 
 
 

hdu 1258 Sum It Up


联系
我们