首页 > 代码库 > HDU 1015 dfs回溯
HDU 1015 dfs回溯
题目真长。。。。。看了好长时间才看懂。。
就是给你一个32位数字和一个最多15个字符的字符串,从字符串中选出5个字符,若满足题中给的那个式子,输出字典序最大的那5个字符,若不满足,输出no solution。
为了解决字典序问题,在输入字符串后,把字符串按从大到小排一下序,搜索一下若满足条件输出即可。
贴代码。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 7 int num; 8 char a[15], b[15]; //a是原串,b储存答案。 9 int flag[15]; //标记a中元素是否使用。 10 int n, f; 11 12 bool cmp(int x,int y) //排序 13 { 14 return x>y; 15 } 16 17 void dfs(int k) 18 { 19 if(f) return; //满足条件一层层返回 20 if(k==5) 21 { 22 int sum=b[0]-b[1]*b[1]+b[2]*b[2]*b[2]-b[3]*b[3]*b[3]*b[3]+b[4]*b[4]*b[4]*b[4]*b[4]; 23 if(sum==num) 24 { 25 for(int i=0;i<5;i++) 26 { 27 char c=b[i]-1+‘A‘; 28 printf("%c",c); 29 } 30 cout<<endl; 31 f=1; 32 } 33 return; 34 } 35 for(int i=0;i<n;i++) 36 { 37 if(!flag[i]) 38 { 39 flag[i]=1; 40 b[k]=a[i]; 41 dfs(k+1); 42 flag[i]=0; //别忘了释放 43 } 44 } 45 } 46 main() 47 { 48 int i, j, k; 49 while(scanf("%d%s",&num,a)!=EOF&&strcmp(a,"END")) 50 { 51 memset(flag,0,sizeof(flag)); 52 n=strlen(a); 53 for(i=0;i<n;i++) 54 a[i]=a[i]-‘A‘+1; 55 sort(a,a+n,cmp); 56 f=0; 57 dfs(0); 58 if(!f) printf("no solution\n"); 59 } 60 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。