DFS/BFS简介以及剪枝本领

DFS简介

[size=4
]DFS寄义 ⭐

DFS，即Depth-first-search，是深度优先搜刮的简称。
它的重要思绪是不停沿当前分支搜刮，当搜刮到止境之后返回，再渐渐向其他地方扩散。
我们可以通过一个树形布局分析DFS的遍历次序

1.         A
2.       / | \
3.      B  C  D
4.     / \    |
5.    E   F   G
6.   / \
7. H   I

复制代码

遍历次序&#xff1
a;(假设不停沿左分支走)
A→B→E→H→I→F→C→D→G
固然，完全可以沿右分支先走，以致遍历出发点并不非得是树的顶端。
究竟上，DFS的实现依赖于递归，而遍历的次序也和递归的位置痛痒相干。
以致通过调解递归的次序，我们可以用三种方法遍历一个二叉树，不外这并不是本次重点，不外多叙述
接下来让我们通过一个简朴的例题来看看DFS的实现。
[size=4
]环球变暖

P86
6
2 [蓝桥杯 201
8 省 AB] 环球变暖
标题形貌

你有一张某海疆                               N                      ×                      N                          N \times N               N×N 像素的照片，. 表现海洋、 # 表现陆地，如下所示&#xff1
a;

1. .......
2. .##....
3. .##....
4. ....##.
5. ..####.
6. ...###.
7. .......

复制代码

此中 “上下左右” 四个方向上连在一起的一片陆地构成一座岛屿。比方上图就有                               2                          2               2 座岛屿。
由于环球变暖导致了海面上升，科学家猜测未来几十年，岛屿边沿一个像素的范围会被海水淹没。详细来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。
比方上图中的海疆未来会变成如下样子&#xff1
a;

1. .......
2. .......
3. .......
4. .......
5. ....#..
6. .......
7. .......

复制代码

请你盘算&#xff1
a;依照科学家的猜测，照片中有多少岛屿会被完全淹没。
输入格式

第一行包罗一个整数                               N                          N               N。                              (                      1
                      ≤                      N                      ≤                      1
000                      )                          (1
\le N \le 1
000)               (1
≤N≤1
000)。
以下                               N                          N               N 行                               N                          N               N 列代表一张海疆照片。
照片包管第                               1
                          1
               1
行、第                               1
                          1
               1
列、第                               N                          N               N 行、第                               N                          N               N 列的像素都是海洋。
输特别式

一个整数表现答案。
输入输出样例 #1


输入 #1

1. 7 .......
2. .##....
3. .##....
4. ....##.
5. ..####.
6. ...###.
7. .......

复制代码

输出 #1

1. 1

复制代码

分析/提示

时限 1
秒, 256
M。蓝桥杯 201
8 年第九届省赛
题解

这是一个连通性标题，要把图内全部联通的点都遍历一次，可以利用DFS去遍历。
DFS遍历的格式大概是

1. void dfs(){
2.     if(已遍历完){
3.         记录
4.         return;
5.     }
6.     for(...){//枚举情况
7.         if(遍历过)
8.             continue;
9.         记录此点
10.         dfs();
11.         回溯
12.     }
13. }

复制代码

观察可知，此题须要我们不停向附近扩散纪录联通地区。
解题思绪大概是&#xff1
a;
先对输入数据预处理处罚，令我们可以通过二维数组中的值得知这块陆地四周有几个岛屿。
然后每次查抄，都把一整片岛屿标志为已查抄，在这个过程中探求有没有四周有四块陆地的点。如果有，分析这个岛屿不会被淹没。
而这个查抄的过程就可以通过DFS递归来实现&#xff1
a;
每次查抄完一块陆地都查抄这块陆地四周的陆地有没有                               4
                          4
               4

末了到达同时遍历一整块岛屿的效果。
此中，关键在于DFS递归时的退出条件以及准确清空已经遍历过的岛屿，制止死循环。
代码

1. #include<iostream>using namespace std;int map[1
2. 002][1
3. 002]&#6
4. 1
5. ;{0};void doo(int i,int j){    if(map[i][j-1
6. ])        map[i][j]&#4
7. 3;&#4
8. 3;;    if(map[i][j&#4
9. 3;1
10. ])        map[i][j]&#4
11. 3;&#4
12. 3;;    if(map[i&#4
13. 3;1
14. ][j])        map[i][j]&#4
15. 3;&#4
16. 3;;    if(map[i-1
17. ][j])        map[i][j]&#4
18. 3;&#4
19. 3;;}void check(int i,int j,bool&flag){    if(map[i][j]&#6
20. 1
21. ;&#6
22. 1
23. ;0)        return;    if(map[i][j]&#6
24. 1
25. ;&#6
26. 1
27. ;5)        flag&#6
28. 1
29. ;1
30. ;    map[i][j]&#6
31. 1
32. ;0;    check(i&#4
33. 3;1
34. ,j,flag);check(i-1
35. ,j,flag);check(i,j&#4
36. 3;1
37. ,flag);check(i,j-1
38. ,flag);    return;}int main(){    int n;    cin>>n;    for(int i&#6
39. 1
40. ;0;i<n;i&#4
41. 3;&#4
42. 3;)        for(int j&#6
43. 1
44. ;0;j<n;j&#4
45. 3;&#4
46. 3;){            char temp;            cin>>temp;            if(temp&#6
47. 1
48. ;&#6
49. 1
50. ;'#')                map[i][j]&#6
51. 1
52. ;1
53. ;            else                map[i][j]&#6
54. 1
55. ;0;        }    for(int i&#6
56. 1
57. ;0;i<n;i&#4
58. 3;&#4
59. 3;)        for(int j&#6
60. 1
61. ;0;j<n;j&#4
62. 3;&#4
63. 3;){            if(map[i][j]&#6
64. 1
65. ;&#6
66. 1
67. ;0)                continue;            doo(i,j);        }    int ans&#6
68. 1
69. ;0;    for(int i&#6
70. 1
71. ;0;i<n;i&#4
72. 3;&#4
73. 3;)        for(int j&#6
74. 1
75. ;0;j<n;j&#4
76. 3;&#4
77. 3;){            if(map[i][j]&#6
78. 1
79. ;&#6
80. 1
81. ;0)                continue;            bool flag&#6
82. 1
83. ;0;            check(i,j,flag);            if(flag&#6
84. 1
85. ;&#6
86. 1
87. ;0)                ans&#4
88. 3;&#4
89. 3;;        }    cout<<ans;    return 0;}

复制代码

DFS练习标题&#xff1
a;发起看完剪枝本领再做此中难度较高的题
P1
21
9八皇后
P1
01
9单词接龙
P51
94
Scales S
BFS简介 ⭐⭐

[size=4
]BFS寄义

BFS指广度优先搜刮。与DFS的区别在于，bfs的遍历次序并不是优先搜刮到分支的止境，而是先遍历完当前层的全部节点，再扩散到下一层。
如许的长处在于，并不须要遍历完一整个分支，而是尽大概判定多个分支，在办理最短路径标题时非常良好，由于在找到最短路径后就可以退出。
让我们通过一个简朴的树形布局观察一下BFS的遍历次序

1.         A
2.       / | \
3.      B  C  D
4.     / \    |
5.    E   F   G
6.   / \
7. H   I

复制代码

遍历次序&#xff1
a;A→B→C→D→E→F→G→H→I
显然 BFS在遍历到                               C                          C               C 的时间就会发现，这是如今最短的路径，因此BFS在完成最短路径，最少步数标题时更为便捷。
我们还是通过同一个例题来看看BFS怎样实现，以便感受DFS和BFS的雷同与差异
[size=4
]环球变暖

题干请看上一节，不再赘述。
题解

DFS的实现依赖于递归，也就是栈，先辈后出。
相应的，BFD的实现依赖于队列，先辈先出。
对于每个节点，BFS会先把当前节点出队，然后把该节点的全部子节点入队，云云反复直到队列为空。
如许可以包管队列中永久只有两层节点，由于父层节点遍历完之后子层节点才会开始弹出并放入新的子节点。
对于环球变暖这道题来说，BFS就是不停把陆地弹出，然后把这个陆地联通的的全部陆地入队。在这个过程中不停标志那些节点已经访问过，就实现了BFS遍历联通的全部陆地。
在BFS的实现中，由于父节点与子节点精密练习，以是只须要观察当前陆地联通的四块是不是都是陆地就可以判定有没有被淹没。
注意标志是否访问过数组上的点。

1. #include <bits/stdc&#4
2. 3;&#4
3. 3;.h>using namespace std;int my_map[1
4. 002][1
5. 002]&#6
6. 1
7. ;{0},vis[1
8. 001
9. ][1
10. 001
11. ];int arounds[4
12. ][2]&#6
13. 1
14. ;{{-1
15. ,0},{1
16. ,0},{0,1
17. },{0,-1
18. }};bool flag;void bfs(int x,int y){//一次BFS，把全部相干元素入队，标志，检测    queue<pair<int,int>> q;    vis[x][y]&#6
19. 1
20. ;1
21. ;    q.push({x,y});        while(!q.empty()){        pair<int,int> tempPair&#6
22. 1
23. ;q.front();        q.pop();        int tempX&#6
24. 1
25. ;tempPair.first,tempY&#6
26. 1
27. ;tempPair.second;        int count&#6
28. 1
29. ;0;        for(int i&#6
30. 1
31. ;0;i<4
32. ;i&#4
33. 3;&#4
34. 3;){            int tx&#6
35. 1
36. ;tempX&#4
37. 3;arounds[i][0],ty&#6
38. 1
39. ;tempY&#4
40. 3;arounds[i][1
41. ];            if(my_map[tx][ty]&#6
42. 1
43. ;&#6
44. 1
45. ;1
46. ){                count&#4
47. 3;&#4
48. 3;;                if(vis[tx][ty]&#6
49. 1
50. ;&#6
51. 1
52. ;0){                    vis[tx][ty]&#6
53. 1
54. ;1
55. ;                    q.push({tx,ty});                }            }        }        if(count&#6
56. 1
57. ;&#6
58. 1
59. ;4
60. )            flag&#6
61. 1
62. ;1
63. ;    }    return;}int main(){    int n;    cin>>n;    for(int i&#6
64. 1
65. ;0;i<n;i&#4
66. 3;&#4
67. 3;)        for(int j&#6
68. 1
69. ;0;j<n;j&#4
70. 3;&#4
71. 3;){            char temp;            cin>>temp;            if(temp&#6
72. 1
73. ;&#6
74. 1
75. ;'#')                my_map[i][j]&#6
76. 1
77. ;1
78. ;        }    int ans&#6
79. 1
80. ;0;    for(int i&#6
81. 1
82. ;0;i<n;i&#4
83. 3;&#4
84. 3;){        for(int j&#6
85. 1
86. ;0;j<n;j&#4
87. 3;&#4
88. 3;){                      if(vis[i][j]&#6
89. 1
90. ;&#6
91. 1
92. ;0&&my_map[i][j]){                flag&#6
93. 1
94. ;0;                bfs(i,j);                if(flag&#6
95. 1
96. ;&#6
97. 1
98. ;0)                    ans&#4
99. 3;&#4
100. 3;;            }         }    }    cout<<ans;    return 0;}

复制代码

剪枝本领 ⭐⭐⭐⭐

⭐表现难度&#xff1
a;
[size=4
]可行性剪枝 ⭐

Count that cows
FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为                               x                          x               x 和                               y                          y               y，假定牛在原地不动。FJ 的行走方式很特别&#xff1
a;他每一次可从进步一步、退却一步大概直接走到                               2                      ×                      x                          2\times x               2×x 的位置。盘算他至少须要几步追上他的牛。
第一举动一个整数                               t                                             (                      1
                      ≤                      t                      ≤                      1
0                      )                          t\ ( 1
\le t\le 1
0)               t (1
≤t≤1
0)，表现数据组数&#xff1
b;
接下来每行包罗一个两个正整数                               x                      ,                      y                                             (                      0                      <                      x                      ,                      y                      ≤                      1
                               0                         5                              )                          x,y\ (0<x,y \le 1
0^5)               x,y (0<x,y≤1
05)，分别表现 FJ 和牛的坐标。
对于每组数据，输出最少步数。
输入&#xff1
a;

1. 1
2. 5 1
3. 7

复制代码

输出&#xff1
a;

1. 4

复制代码

题解&#xff1
a;

可行性剪枝是最为简朴、直观的一种剪枝本领。
纵然没有特意学过剪枝，只打仗过根本的DFS与BFS概念的同砚也大概独立想出。
其本质是&#xff1
a;确定当前环境已经不合法，就不须要再做剩下的“无谓”运算去探求答案，而是直接把这一分支砍掉。
在本题中，显然当位置小于牛时，可以选择进一步，退一步和乘二，它们分别代表三种大概性。
但当位置大于牛时，无论是进一步还是乘二，都不大概靠近答案，因此这是“不可行”的分支，须要砍去。
本题也利用了哈希表去判重剪枝，详细可参考下面的BFS去重剪枝
代码&#xff1
a;

1. #include <iostream>#include<queue>#include<unordered_set>using namespace std;unordered_set<int> my_set;int bfs(int x,int y){        if(x&#6
2. 1
3. ;&#6
4. 1
5. ;y)                return 0;        queue<pair<int,int>> q;        q.push({x,0});        my_set.insert(x);        while(q.size()){                pair<int,int> a&#6
6. 1
7. ;q.front();                q.pop();                int num&#6
8. 1
9. ;a.first,steps&#6
10. 1
11. ;a.second;                if(num&#6
12. 1
13. ;&#6
14. 1
15. ;y){                        return steps;                 }else if(num>y){//可行性剪枝                        if(!my_set.count(num-1
16. )){                                q.push({num-1
17. ,steps&#4
18. 3;1
19. });                                my_set.insert(num-1
20. );                        }                }else{                        if(!my_set.count(num-1
21. )){                                q.push({num-1
22. ,steps&#4
23. 3;1
24. });                                my_set.insert(num-1
25. );                        }                        if(!my_set.count(num&#4
26. 3;1
27. )){                                q.push({num&#4
28. 3;1
29. ,steps&#4
30. 3;1
31. });                                my_set.insert(num&#4
32. 3;1
33. );                        }                        if(!my_set.count(num*2)){                                q.push({num*2,steps&#4
34. 3;1
35. });                                my_set.insert(num*2);                        }                }        }        return -1
36. ;}int main(){                int t;        cin>>t;        for(int i&#6
37. 1
38. ;0;i<t;i&#4
39. 3;&#4
40. 3;){                int x,y;                cin>>x>>y;                my_set.clear();                cout<<bfs(x,y)<<endl;        }        return 0;}

复制代码

[size=4
]最优性剪枝 ⭐⭐⭐

P1
1
1
8 [USACO06
FEB] Backward Digit Sums G/S
标题形貌
游戏形貌
有这么一个游戏&#xff1
a;
写出一个                               1
                      ∼                      n                          1
\sim n               1
∼n 的分列                               a                          a               a，然后每次将相邻两个数相加，构成新的序列，再对新序列举行如许的利用。
显然每次构成的序列都比上一次的序列长度少                               1
                          1
               1
，直到只剩下一个数字位置。

1.     3   1
2.    2   4
3.       4
4.    3   6
5.         7   9         1
6. 6

复制代码

任务要求
如今要倒着玩这个游戏。如果知道                               n                          n               n 和终极得到的数字的巨细 sum，请你求出最初的序列                               a                          a               a。
注意&#xff1
a;如果有多种答案，要求输出字典序最小的那一个。
字典序
我们称序列                               a                      &#6
1
;                      ⟨                               a                         1
                              ,                               a                         2                              ,                      …                      ,                               a                         n                              ⟩                          a &#6
1
; \langle a_1
, a_2, \dots, a_n \rangle               a&#6
1
;⟨a1
​,a2​,…,an​⟩ 的字典序小于序列                               b                      &#6
1
;                      ⟨                               b                         1
                              ,                               b                         2                              ,                      …                      ,                               b                         n                              ⟩                          b &#6
1
; \langle b_1
, b_2, \dots, b_n \rangle               b&#6
1
;⟨b1
​,b2​,…,bn​⟩ 的字典序，当且仅当存在一个位置                               p                          p               p，满足&#xff1
a;
                                        a                         1
                              &#6
1
;                               b                         1
                              ,                               a                         2                              &#6
1
;                               b                         2                              ,                      …                      ,                               a                                   p                            −                            1
                                       &#6
1
;                               b                                   p                            −                            1
                                           a_1
&#6
1
; b_1
, a_2 &#6
1
; b_2, \dots, a_{p-1
} &#6
1
; b_{p-1
}               a1
​&#6
1
;b1
​,a2​&#6
1
;b2​,…,ap−1
​&#6
1
;bp−1
​，
且                                        a                         p                              <                               b                         p                                  a_p < b_p               ap​<bp​。
输入&#xff1
a;共一行两个正整数                               n                      ,                      s                      u                      m                          n,sum               n,sum。
输出&#xff1
a;输出包罗一行，为字典序最小的谁人答案。
当无解的时间，请什么也不输出。
输入 #1

1. 4
2. 1
3. 6

复制代码

输出 #1

1. 3 1
2. 2 4

复制代码

分析/提示

• 对于                                    4
  0                         %                              4
  0\%                  4
  0% 的数据，                                   1
                           ≤                         n                         ≤                         7                              1
  \le n\le 7                  1
  ≤n≤7&#xff1
  b;
  
• 对于                                    80                         %                              80\%                  80% 的数据，                                   1
                           ≤                         n                         ≤                         1
  0                              1
  \le n \le 1
  0                  1
  ≤n≤1
  0&#xff1
  b;
  
• 对于                                    1
  00                         %                              1
  00\%                  1
  00% 的数据，                                   1
                           ≤                         n                         ≤                         1
  2                              1
  \le n \le 1
  2                  1
  ≤n≤1
  2，                                   1
                           ≤                         s                         u                         m                         ≤                         1
  234
  5                              1
  \le sum\le 1
  234
  5                  1
  ≤sum≤1
  234
  5。
  

题解&#xff1
a;

本题重要运用的剪枝本领是对杨辉三角预处理处罚，以及最优性剪枝。
对杨辉三角的预处理处罚是在于，如果须要调用组合数的话，可以先把杨辉三角存入全局数组方便调用，不多赘述。
最优性剪枝指 如果当前答案的最大大概值都无法高出如今的最优答案，那么就可以直接舍弃当前分支。
这是一种求解最优标题标剪枝思绪。
回到本题，本题思绪大概是&#xff1
a;通过dfs对1
到n的数字全分列，当其杨辉三角和为sum时即找到准确答案。
dfs从小到大遍历可包管第一个答案是字典序最小的答案。
最优化剪枝的应用在于对如今截取出来的数字串举行处理处罚，盘算其大概的值，若如今列出的值已经高出sum，则应当剪去该分支。

1. #include<iostream>#include<algorithm>#include<vector>using namespace std;int n,sum,flag;int numbers[1
2. 3]&#6
3. 1
4. ;{0,1
5. ,2,3,4
6. ,5,6
7. ,7,8,9,1
8. 0,1
9. 1
10. ,1
11. 2};vector<int> temp;vector<int> yhsj[1
12. 3] &#6
13. 1
14. ; {    {0},        // 第 0 行（可忽略）    {1
15. },        // 第 1
16. 行    {1
17. , 1
18. },     // 第 2 行    {1
19. , 2, 1
20. },  // 第 3 行    {1
21. , 3, 3, 1
22. },    {1
23. , 4
24. , 6
25. , 4
26. , 1
27. },    {1
28. , 5, 1
29. 0, 1
30. 0, 5, 1
31. },    {1
32. , 6
33. , 1
34. 5, 20, 1
35. 5, 6
36. , 1
37. },    {1
38. , 7, 21
39. , 35, 35, 21
40. , 7, 1
41. },    {1
42. , 8, 28, 56
43. , 70, 56
44. , 28, 8, 1
45. },    {1
46. , 9, 36
47. , 84
48. , 1
49. 26
50. , 1
51. 26
52. , 84
53. , 36
54. , 9, 1
55. },    {1
56. , 1
57. 0, 4
58. 5, 1
59. 20, 21
60. 0, 252, 21
61. 0, 1
62. 20, 4
63. 5, 1
64. 0, 1
65. },    {1
66. , 1
67. 1
68. , 55, 1
69. 6
70. 5, 330, 4
71. 6
72. 2, 4
73. 6
74. 2, 330, 1
75. 6
76. 5, 55, 1
77. 1
78. , 1
79. }};void dfs(int count,int nowSum){//预备取第count个    for(int i&#6
80. 1
81. ;1
82. ;i<&#6
83. 1
84. ;n;i&#4
85. 3;&#4
86. 3;){        if(flag)            return;        if(numbers[i]&#6
87. 1
88. ;&#6
89. 1
90. ;0)            continue;        temp.push_back(i);        numbers[i]&#6
91. 1
92. ;0;        nowSum&#6
93. 1
94. ;nowSum&#4
95. 3;yhsj[n][count-1
96. ]*i;        if(nowSum>sum){            numbers[i]&#6
97. 1
98. ;i;            temp.pop_back();            return;        }else if(nowSum&#6
99. 1
100. ;&#6
101. 1
102. ;sum&&count&#6
103. 1
104. ;&#6
105. 1
106. ;n){            flag&#6
107. 1
108. ;1
109. ;            for(auto& a:temp)                cout<<a<<&#34
110. ; &#34
111. ;;            return;        }        dfs(count&#4
112. 3;1
113. ,nowSum);        nowSum-&#6
114. 1
115. ;yhsj[n][count-1
116. ]*i;        numbers[i]&#6
117. 1
118. ;i;        temp.pop_back();    }    return;}int main(){    cin>>n>>sum;    dfs(1
119. ,0);    return 0;}

复制代码

[size=4
]BFS判重剪枝 ⭐⭐

0跳蚂蚱 蓝桥杯201
7
此题是一个简朴的八数码标题&#xff1
a;
标题形貌

本题为填空题，只须要算出效果后，在代码中利用输出语句将所填效果输出即可。
如下图所示&#xff1
a;

有 9 只盘子，排成 1
个圆圈。此中 8 只盘子内装着 8 只蚱蜢，有一个是空盘。
我们把这些蚱蜢顺时针编号为 1
~ 8。
规则
每只蚱蜢都可以&#xff1
a;
跳到相邻的空盘中。
也可以用力一点，越过一个相邻的蚱蜢 跳到空盘中。
目标
请盘算至少要颠末多少次跳跃，才气使蚱蜢们的队形改为按照逆时针分列，而且保持空盘的位置稳固。
题解

我们可以将标题视作是空盘与相邻盘的置换，每次有四种置换的大概。
不停置换，得到答案后返回。
求解最短次数，显然用BFS办理。
但是，如果空盘与右边盘子交换后，又与左侧盘子交换。左换右，右换左，无穷无尽，陷入死循环。
因此我们须要判定一种大概性有没有出现过，如果它出现过，那么它延伸出的全部分支都会位于队列中，不须要重复盘算。
可以利用哈希表办理这个标题。
别的，盘算BFS复杂标题标步数时，可以接纳pair或布局体纪录层数。
代码&#xff1
a;

1. #include <iostream>#include<queue>#include<unordered_set>using namespace std;struct node{        string s;        int step;        int index_0;        node(string s&#6
2. 1
3. ;&#34
4. ;&#34
5. ;,int step&#6
6. 1
7. ;0,int index_0&#6
8. 1
9. ;0):s(s),step(step),index_0(index_0){};};int main(){                node a;        unordered_set<string> mm;        a.s&#6
10. 1
11. ;&#34
12. ;01
13. 234
14. 56
15. 78&#34
16. ;;a.step&#6
17. 1
18. ;0;a.index_0&#6
19. 1
20. ;0;        queue<node> q;//把布局体入队        int op[]&#6
21. 1
22. ;{-2,-1
23. ,1
24. ,2};        q.push(a);        node ans;        mm.insert(a.s);        while(q.size()){                node now&#6
25. 1
26. ;q.front();                q.pop();                int Now_0&#6
27. 1
28. ;now.index_0;                string nowS&#6
29. 1
30. ;now.s;                for(int i&#6
31. 1
32. ;0;i<4
33. ;i&#4
34. 3;&#4
35. 3;){                        int nI&#6
36. 1
37. ;(Now_0&#4
38. 3;op[i]&#4
39. 3;9)%9;//得到新位置                        string temp&#6
40. 1
41. ;nowS;                        temp[Now_0]&#6
42. 1
43. ;temp[nI];                        temp[nI]&#6
44. 1
45. ;'0';                        if(mm.find(temp)!&#6
46. 1
47. ;mm.end())//如果已经有了                                continue;                        mm.insert(temp);                        node b(temp,now.step&#4
48. 3;1
49. ,nI);                        if(temp&#6
50. 1
51. ;&#6
52. 1
53. ;&#34
54. ;0876
55. 54
56. 321
57. &#34
58. ;)                                ans&#6
59. 1
60. ;b;                        if(ans.step)                                break;                        q.push(b);                }                if(ans.step)                        break;        }        cout<<ans.step;        return 0;}

复制代码

[size=4
]搜刮次序剪枝 ⭐⭐⭐⭐

P1
1
20小木棍:较难
标题形貌

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不高出                               50                          50               50。
如今，他想把小木棍拼接成原来的样子，但是却忘记了本身开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小大概长度。
输入格式
第一行是一个整数                               n                          n               n，表现小木棍的个数。
第二行有                               n                          n               n 个整数，表现各个木棍的长度                                        a                         i                                  a_i               ai​。
输特别式
输出一行一个整数表现答案。
输入 #1

1. 95 2 1
2. 5 2 1
3. 5 2 1

复制代码

输出 #1

1. 6

复制代码

对于全部测试点，                              1
                      ≤                      n                      ≤                      6
5                          1
\leq n \leq 6
5               1
≤n≤6
5，                              1
                      ≤                               a                         i                              ≤                      50                          1
\leq a_i \leq 50               1
≤ai​≤50。
题解

阅读题干，想到实行暴力深搜，只须要把每个大概的长度罗列出来，对每个长度举行DFS，看看可否拼接玉成部是这个长度的长木棍即可。
如果全部都乐成拼接，则输出答案，如果不可，则继承搜刮。
此题关键在于暴力搜刮的时间复杂度过高，须要极强的剪枝本领。
搜刮次序剪枝是指，按肯定的次序去搜刮，可以有效制止产生大量的无效分支。
对于本题而言，无论木棍好坏，都总是要拼接进去的，那么如果先实行长的小木棍，就可以快速把长度积累到目标值附近，大概直接判定出不大概拼接出目标值（若目标值太小）。
而把小木棍放前面则会产生大量冗杂的大概性。
因此，可以先对数组举行降序处理处罚，再继承DFS搜刮。
别的。本题另有许多独属于此题的剪枝本领，由于没有太多的可重复性，以是在此仅简朴提及，有爱好的同砚可以观看洛谷题解&#xff1
a;
1
、排序之后可以通过预处理处罚出next数组，如果一个长度的小木棍不符合，就快速跳到下一个长度的木棍区间，而不是一个一个检索。
2、若本次恰好可以构成一个长木棍，但是反面的拼接失败了，那么不须要在本次DFS的底子之上再搜刮，而是直接return。
由于把恰好能构成木棍的放入一定是最优解，如果如许都不可，那无论怎么调解都是不可的。
3、先把大概的答案预处理处罚一下，由于答案只大概是总和的因数。
从小到大查抄答案，查抄到的第一个肯定是最小的，直接输出即可。

1. #include<bits/stdc&#4
2. 3;&#4
3. 3;.h>using namespace std;int nums[1
4. 00],vis[1
5. 00],len,sum,currentLen,nes[1
6. 00];bool Answer_right&#6
7. 1
8. ;0;inline vector<int> maybeAnswer();void dfs(const int& d,int nowOper,const int& total,int startCount){    if(currentLen&#6
9. 1
10. ;&#6
11. 1
12. ;d){//进入下一组循环        if(total&#6
13. 1
14. ;&#6
15. 1
16. ;nowOper){            Answer_right&#6
17. 1
18. ;1
19. ;            return;        }        currentLen&#6
20. 1
21. ;0;        dfs(d,nowOper&#4
22. 3;1
23. ,total,0);    }else{//还是小于                //在DFS的进程中已经有了一个CurrentLen，如今想获取下一个加进当前len的值        for(int i&#6
24. 1
25. ;startCount;i<len;i&#4
26. 3;&#4
27. 3;){            if(vis[i]) continue;            if(currentLen&#4
28. 3;nums[i]>d){//如果大，下一个                i&#6
29. 1
30. ;nes[i]-1
31. ;                continue;            }            vis[i]&#6
32. 1
33. ;1
34. ;            currentLen&#4
35. 3;&#6
36. 1
37. ;nums[i];            int newStart&#6
38. 1
39. ;i;            while(newStart>&#6
40. 1
41. ;0&&nums[newStart]&#6
42. 1
43. ;&#6
44. 1
45. ;nums[i])                newStart--;            dfs(d,nowOper,total,newStart);            if(Answer_right)                return;            currentLen-&#6
46. 1
47. ;nums[i];            vis[i]&#6
48. 1
49. ;0;            if(currentLen&#4
50. 3;nums[i]&#6
51. 1
52. ;&#6
53. 1
54. ;d)                return;            i&#6
55. 1
56. ;nes[i]-1
57. ;            if(i&#6
58. 1
59. ;&#6
60. 1
61. ;len-1
62. )                return;        }    }    return;}int main(){    cin>>len;    for(int i&#6
63. 1
64. ;0;i<len;i&#4
65. 3;&#4
66. 3;){        cin>>nums[i];        sum&#4
67. 3;&#6
68. 1
69. ;nums[i];    }    sort(nums,nums&#4
70. 3;len,greater<int>());    for(int slow&#6
71. 1
72. ;0;slow<len;slow&#4
73. 3;&#4
74. 3;){        int fast&#6
75. 1
76. ;slow&#4
77. 3;1
78. ;        while(fast<len&&nes[fast]&#6
79. 1
80. ;&#6
81. 1
82. ;nums[slow])            fast&#4
83. 3;&#4
84. 3;;        nes[slow]&#6
85. 1
86. ;fast;    }        vector<int> d_s&#6
87. 1
88. ;maybeAnswer();    for(auto& d:d_s){        dfs(d,1
89. ,sum/d,0);        currentLen&#6
90. 1
91. ;0;        if(Answer_right){            cout<<d;            break;        }    }    return 0;}inline vector<int> maybeAnswer(){    vector<int> res;    for(int i&#6
92. 1
93. ;1
94. ;i*i<&#6
95. 1
96. ;sum;i&#4
97. 3;&#4
98. 3;){        if(sum%i&#6
99. 1
100. ;&#6
101. 1
102. ;0){            res.push_back(i);            if(sum/i!&#6
103. 1
104. ;i)                res.push_back(sum/i);        }    }    sort(res.begin(),res.end());    return res;}

复制代码

23.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。