首页 > 代码库 > HDU 1015 dfs回溯

HDU 1015 dfs回溯

2024-07-06 10:11:51   229人阅读

题目真长。。。。。看了好长时间才看懂。。

就是给你一个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 }

 


联系
我们