backtracking算法

搞清楚回溯体，穷举多维度值，维度一定会加一

数值一定很小。搞清楚怎么处理输入输出。

有一定的模版。

uva,112

这种思想和获取方式是我所追求的。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 enum{
 6     LEFT_BRACKET,RIGHT_BRACKET,NUMBER,
 7     
 8     MATCH,NOT_MATCH,EMPTY_TREE
 9 };
10 
11 static int num;
12 
13 int getToken()
14 {
15     char c=getchar();
16     
17     while(c==' ' || c=='
')
18         c=getchar();
19     
20     num=0;
21     if(c=='(')
22         return LEFT_BRACKET;
23     else if(c==')')
24         return RIGHT_BRACKET;
25     else if((c>='0' && c<='9') || c=='-')
26     {
27         int sign=1;
28         
29         if(c=='-')
30         {
31             sign=-1;
32             c=getchar();
33         }
34         
35         for(;c>='0' && c<='9';c=getchar())
36         {
37             num=num*10+c-'0';
38         }
39         num*=sign;
40         ungetc(c,stdin);
41         return NUMBER;
42     }
43     return 0;
44 }
45 
46 int traversal(int sum,int target)
47 {
48     getToken();
49     int token=getToken();
50     
51     if(token==RIGHT_BRACKET)
52         return EMPTY_TREE;
53     else sum+=num;
54     
55     int lc=traversal(sum,target);
56     int rc=traversal(sum,target);
57     
58     getToken();
59     
60     if(lc==EMPTY_TREE && rc==EMPTY_TREE)
61         if(sum==target)
62             return MATCH;
63     
64     if(lc==MATCH || rc==MATCH)
65         return MATCH;
66     return NOT_MATCH;
67 }
68 
69 int main()
70 {
71     int target;
72     while(~scanf("%d",&target))
73     {
74         if(traversal(0,target)==MATCH)
75             printf("yes
");
76         else
77             printf("no
");
78     }
79     return 0;
80 }

View Code

cin.peek(),cin.ignore(),cin.putback()的输入流的方法

 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 void spaces()
 7 {
 8     while(cin.peek()==' '||cin.peek()=='
')
 9         cin.ignore(1);
10 }
11 
12 bool node(int sum,int target,bool *output)
13 {
14     int sign=1,v;
15     spaces();
16     cin.ignore(1);
17     spaces();
18     if(cin.peek()==')')
19     {
20         cin.ignore(1);
21         return sum==target;
22     }
23     spaces();
24     if(cin.peek()=='-')
25     {
26         sign=-1;
27         cin.ignore(1);
28     }
29     
30     cin>>v;
31     v*=sign;
32     
33     int n1=node(sum+v,target,output);
34     int n2=node(sum+v,target,output);
35     
36     if(n1 && n2)
37         *output=true;
38     spaces();
39     cin.ignore(1);
40     return false;
41 }
42 
43 int main()
44 {
45     int target;
46     bool output;
47     while(~scanf("%d",&target))
48     {
49         output=false;
50         node(0,target,&output);
51         if(output)
52             printf("yes
");
53         else
54             printf("no
");
55     }
56     return 0;
57 }

View Code

uva,167

考虑全面。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 int l[8],r[8],md1[20],md2[20];//数组开大一点
 9 int squares[10][10];
10 int maxscores;
11 int sum;
12 
13 void reversal(int x)
14 {
15     int y;
16     if(x==8)
17     {
18         if(sum>maxscores)
19             maxscores=sum;
20         return;
21     }
22     
23     for(y=0;y<8;y++)  //考虑一行的8个点，一开始只考虑了一个点所以错了
24     {//四条线，横竖斜线要记录就不可以放了
25         if(l[x] && r[y] && md1[x-y+8] && md2[x+y])
26         {//放皇后
27             l[x]=0,r[y]=0,md1[x-y+8]=0,md2[x+y]=0;
28             sum+=squares[x][y];
29             reversal(x+1);
30             //不放皇后
31             l[x]=1,r[y]=1,md1[x-y+8]=1,md2[x+y]=1;
32             sum-=squares[x][y];
33         }
34     }
35 }
36 
37 int main()
38 {
39     int k;
40     scanf("%d",&k);
41     while(k--)
42     {
43         for(int i=0;i<8;i++)
44             for(int j=0;j<8;j++)
45                 scanf("%d",&squares[i][j]);
46         memset(l,1,sizeof(l));
47         memset(r,1,sizeof(r));
48         memset(md1,1,sizeof(md1));
49         memset(md2,1,sizeof(md2));
50         maxscores=0;
51         sum=0;
52         reversal(0);
53         printf("%5d
",maxscores);
54     }
55     return 0;
56 }

View Code

uva,216

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 #define inf 1e9
 8 
 9 struct node
10 {
11     double x,y;
12 }p[10];
13 
14 double dis(node a,node b)
15 {
16     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
17 }
18 
19 bool vis[10];
20 int pre[10];
21 int print[10];
22 double minx;
23 int n;
24 
25 void reversal(int cur,double sum)
26 {
27     if(cur==n)
28     {
29         if(sum<minx)
30         {
31             minx=sum;
32             memcpy(print,pre,sizeof(pre));
33         }
34         return;
35     }
36     
37     for(int i=0;i<n;i++)
38     {
39         if(vis[i]) continue;
40         vis[i]=true;
41         pre[cur]=i;
42         if(cur==0)
43             reversal(cur+1,0);
44         else
45         {
46             double t=dis(p[pre[cur]],p[pre[cur-1]]);
47             reversal(cur+1,sum+t+16);
48         }
49         
50         vis[i]=false;
51     }
52 }
53 
54 int main()
55 {
56     int cas=1;
57     while(scanf("%d",&n),n)
58     {
59         for(int i=0;i<n;i++)
60         {
61             scanf("%lf%lf",&p[i].x,&p[i].y);
62             pre[i]=i;
63         }
64         memset(vis,false,sizeof(vis));
65         minx=inf;
66         reversal(0,0);
67         printf("**********************************************************
");
68         printf("Network #%d
",cas++);
69         for(int i=1;i<n;i++)
70         {
71             double t=dis(p[print[i]],p[print[i-1]]);
72             printf("Cable requirement to connect ");
73             printf("(%d,%d) to (%d,%d) is %.2lf feet.
",(int)p[print[i]].x,(int)p[print[i]].y,(int)p[print[i-1]].x,(int)p[print[i-1]].y,t+16);
74         }
75         printf("Number of feet of cable required is %.2lf.
",minx);
76         
77     }
78 }

View Code

next_permutation做得

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 #define inf 1e9
 8 
 9 struct node
10 {
11     double x,y;
12 }p[10];
13 
14 double dis(node a,node b)
15 {
16     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
17 }
18 
19 bool vis[10];
20 int pre[10];
21 int print[10];
22 double minx;
23 int n;
24 
25 void solve()
26 {
27     double sum=0;
28     for(int i=1;i<n;i++)
29         sum+=dis(p[pre[i]],p[pre[i-1]]);
30     if(sum<minx)
31     {
32         minx=sum;
33         memcpy(print,pre,sizeof(pre));
34     }
35 }
36 
37 int main()
38 {
39     int cas=1;
40     while(scanf("%d",&n),n)
41     {
42         for(int i=0;i<n;i++)
43         {
44             scanf("%lf%lf",&p[i].x,&p[i].y);
45             pre[i]=i;
46         }
47         memset(vis,false,sizeof(vis));
48         minx=inf;
49         do
50         {
51             solve();
52         }while(next_permutation(pre,pre+n));
53         printf("**********************************************************
");
54         printf("Network #%d
",cas++);
55         for(int i=1;i<n;i++)
56         {
57             double t=dis(p[print[i]],p[print[i-1]]);
58             printf("Cable requirement to connect ");
59             printf("(%d,%d) to (%d,%d) is %.2lf feet.
",(int)p[print[i]].x,(int)p[print[i]].y,(int)p[print[i-1]].x,(int)p[print[i-1]].y,t+16);
60         }
61         printf("Number of feet of cable required is %.2lf.
",minx+16*(n-1));
62         
63     }
64 }

View Code

uva,524

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 bool vis[40];
 8 
 9 void Prime()
10 {
11     for(int i=0;i<40;i++)
12         vis[i]=0;
13     for(int i=2;i<40;i++)
14         if(!vis[i])
15         {
16             for(int j=2*i;j<40;j+=i)
17                 vis[j]=1;
18         }
19 }
20 int n;
21 int sol[20];
22 int sel[20];
23 bool used[20];
24 
25 void print_solution()
26 {
27     for(int i=0;i<n;i++)
28     {
29         if(!i)
30             printf("%d",sol[i]);
31         else
32             printf(" %d",sol[i]);
33     }
34     printf("
");
35 }
36 
37 void reversal(int dim)
38 {
39     if(dim==n)
40     {
41         if(!vis[sol[0]+sol[n-1]])
42         {
43             print_solution();
44         }
45         return;
46     }
47     for(int i=1;i<n;i++)
48     {
49         int t=sel[i];
50         if(!used[t] && !vis[sol[dim-1]+t])
51         {
52             used[t]=true;
53             sol[dim]=t;
54             reversal(dim+1);
55             
56             used[t]=false;
57         }
58     }
59     
60 }
61 
62 int main()
63 {
64     int cas=1;
65     Prime();
66     while(~scanf("%d",&n))
67     {
68         if(cas!=1)
69             printf("
");
70         memset(sol,0,sizeof(sol));
71         memset(used,false,sizeof(used));
72         printf("Case %d:
",cas++);
73         for(int i=1;i<n;i++)
74             sel[i]=i+1;
75         sol[0]=1;
76         used[1]=true;
77         reversal(1);
78     }
79     return 0;
80 }

View Code

uva,574

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 int sol[15];
 9 bool vis[15];
10 
11 int a[15];
12 int n;
13 bool flag1;
14 
15 int sum;
16 
17 void print_solution(int tot)
18 {
19     int cnt=0;
20     bool flag=false;
21     for(int i=0;i<tot;i++)
22     {
23         if(sol[i] && !flag)
24         {
25             printf("%d",sol[i]);
26             flag=true;
27             cnt++;
28         }
29         else if(sol[i])
30         {
31             printf("+%d",sol[i]);
32             cnt++;
33         }
34     }
35     printf("
");
36         
37 }
38 
39 void reversal(int t,int sum,int dim)
40 {
41     if(sum==t)
42     {
43         flag1=true;
44         print_solution(dim);
45         return;
46     }
47     
48     int last=0;
49     for(int i=0;i<n;i++)
50     {
51         if(!vis[i])
52         {
53             if(last!=a[i])
54             {
55                 if(sum+a[i]<=t)
56                 {
57                     if(!dim)
58                     {
59                         last=a[i];
60                         vis[i]=true;
61                         sol[dim]=a[i];
62                         reversal(t,sum+a[i],dim+1);
63                         vis[i]=false;
64                     }
65                     else if(a[i]<=sol[dim-1])
66                     {
67                         last=a[i];
68                         vis[i]=true;
69                         sol[dim]=a[i];
70                         reversal(t,sum+a[i],dim+1);
71                         vis[i]=false;
72                     }
73                 }
74             }
75         }
76         
77     }
78     
79 }
80 
81 int main()
82 {
83     int t;
84     while(scanf("%d%d",&t,&n) && n)
85     {
86         for(int i=0;i<n;i++)
87             scanf("%d",&a[i]);
88         printf("Sums of %d:
",t);
89         memset(sol,0,sizeof(sol));
90         memset(vis,false,sizeof(false));
91         flag1=false;
92         reversal(t,0,0);
93         if(!flag1)
94             printf("NONE
");
95     }
96     return 0;
97 }

View Code

活在现实，做在梦里。