本文主要是介绍算法刷题day55：搜索（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
- 引言
- 一、迷宫
- 二、红与黑
- 三、马走日
- 四、单词接龙
- 五、分成互质组
- 六、小猫爬山
- 七、数独
- 八、木棒
- 九、加成序列
- 十、排书
引言
上篇文章主要是讲 B F S BFS BFS 的，主要应用在搜索中找最短路方面，主要就是在内部搜索，和整体搜索。而 D F S DFS DFS 其实就是暴力，主要介绍如果写出暴力，并且写出优化与剪枝，有时候能用 B F S BFS BFS ，就用它，因为不容易失误，但是用 D F S DFS DFS 就是不会的时候用，好处就是可以剪枝。那就还是以题目的方式，进行讲解。
一、迷宫
标签：DFS
思路：其实这道题用 B F S BFS BFS 就是最保险的，因为就是一个基本的最短路，但因为本章节是讲 D F S DFS DFS 的，所以就拿 D F S DFS DFS 写了，也顺便粘一个 B F S BFS BFS 的吧，没什么说的，详情见代码。
题目描述：
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.
和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到
点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。注意：A、B不一定是两个不同的点。输入格式
第1行是测试数据的组数 k，后面跟着 k 组输入。每组测试数据的第1行是一个正整数 n，表示迷宫的规模是 n∗n 的。接下来是一个 n∗n 的矩阵，矩阵中的元素为.或者#。再接下来一行是 4 个整数 ha,la,hb,lb，描述 A 处在第 ha 行, 第 la 列，B 处在第 hb 行, 第 lb 列。注意到 ha,la,hb,lb 全部是从 0 开始计数的。输出格式
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。数据范围
1≤n≤100
输入样例：
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
输出样例:
YES
NO
示例代码1：DFS版
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 110, M = N, INF = 0x3f3f3f3f;int n, m;
char g[N][N];
bool st[N][N];
PII S, E;int dir[4][2] = {0,1,0,-1,1,0,-1,0};bool dfs(int x, int y)
{st[x][y] = true;if(x == E.x && y == E.y) return true;for(int i = 0; i < 4; ++i){int a = x + dir[i][0];int b = y + dir[i][1];if(a < 0 || a >= n || b < 0 || b >= n) continue;if(st[a][b] || g[a][b] == '#') continue;if(dfs(a,b)) return true;}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int T; cin >> T;while(T--){memset(st, 0, sizeof st);cin >> n;for(int i = 0; i < n; ++i) cin >> g[i];cin >> S.x >> S.y >> E.x >> E.y;bool flag;if(g[S.x][S.y] == '#' || g[E.x][E.y] == '#') flag = false;else flag = dfs(S.x,S.y);if(flag) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}
示例代码2：BFS
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 110, M = N, INF = 0x3f3f3f3f;int n, m;
char g[N][N];
bool st[N][N];
PII S, E;int dir[4][2] = {0,1,0,-1,1,0,-1,0};bool bfs()
{if(g[S.x][S.y] == '#' || g[E.x][E.y] == '#') return false; // 没说，起始点可能就是死路memset(st, 0, sizeof st);st[S.x][S.y] = true;queue<PII> q; q.push(S);while(q.size()){auto t = q.front(); q.pop();if(t == E) return true; // 写这里而不是下面，防止起点即终点for(int i = 0; i < 4; ++i){int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= n) continue;if(st[x][y] || g[x][y] == '#') continue;st[x][y] = true;q.push({x,y});}}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int T; cin >> T;while(T--){cin >> n;for(int i = 0; i < n; ++i) cin >> g[i];cin >> S.x >> S.y >> E.x >> E.y;if(bfs()) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}
二、红与黑
标签：DFS、Flood Fill
思路：其实就是找从起点开始能走多少个点，也没啥说的，两个版本都在下面，看看即可。
题目描述：
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。输入格式
输入包括多个数据集合。每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。当在一行中读入的是两个零时，表示输入结束。输出格式
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。数据范围
1≤W,H≤20
输入样例：
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例：
45
示例代码1：DFS
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 25, M = N, INF = 0x3f3f3f3f;int n, m;
char g[N][N];
bool st[N][N];
PII S;int dir[4][2] = {0,1,0,-1,1,0,-1,0};int dfs(int x, int y)
{if(g[x][y] == '#') return 0; // 防止起始点为障碍st[x][y] = true;int res = 1;for(int i = 0; i < 4; ++i){int a = x + dir[i][0];int b = y + dir[i][1];if(a < 0 || a >= n || b < 0 || b >= m) continue;if(st[a][b] || g[a][b] == '#') continue;res += dfs(a,b);}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);while(cin >> m >> n, n || m){memset(st, 0, sizeof st);for(int i = 0; i < n; ++i){cin >> g[i];for(int j = 0; j < m; ++j){if(g[i][j] == '@') S = {i,j};}}cout << dfs(S.x,S.y) << endl;}return 0;
}
示例代码2：BFS
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 25, M = N, INF = 0x3f3f3f3f;int n, m;
char g[N][N];
bool st[N][N];
PII S;int dir[4][2] = {0,1,0,-1,1,0,-1,0};int bfs()
{memset(st, 0, sizeof st);st[S.x][S.y] = true;int res = 1;queue<PII> q; q.push(S);while(q.size()){auto t = q.front(); q.pop();for(int i = 0; i < 4; ++i){int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= m) continue;if(st[x][y] || g[x][y] == '#') continue; // 这里写='#' 是因为起点或者终点是有符号的，而不是!='.' res++;st[x][y] = true;q.push({x,y});}}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);while(cin >> m >> n, n || m) // 看清楚行列顺序 {for(int i = 0; i < n; ++i) {cin >> g[i];for(int j = 0; j < m; ++j){if(g[i][j] == '@') S = {i,j};}}cout << bfs() << endl;}return 0;
}
三、马走日
标签：DFS
思路：整体思想就是每一个点走的八个方向都是一种方案，只要在遍历过程中能把所有点都给走满，就是一种方案。所以可以定义一个全局变量来记录，然后传一个当前走过点的数量，用来判断是否走满了，然后就是正常的写法了，当然也可以让其返回每个方向上的数量，不用全局变量，也是可以的，这里就不写了。
题目描述：
马在中国象棋以日字形规则移动。请编写一段程序，给定 n∗m 大小的棋盘，以及马的初始位置 (x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途
径遍历棋盘上的所有点。输入格式
第一行为整数 T，表示测试数据组数。每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,y。输出格式
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，若无法遍历棋盘上的所有点则输出 0。数据范围
1≤T≤9,1≤m,n≤9,1≤n×m≤28，0≤x≤n−1,0≤y≤m−1
输入样例：
1
5 4 0 0
输出样例：
32
示例代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 10, M = N, INF = 0x3f3f3f3f;int n, m;
bool st[N][N];
PII S;
int ans;int dir[8][2] = {-2,-1, -2,1, -1,-2, -1,2, 1,-2, 1,2, 2,-1, 2,1};void dfs(int cur, int x, int y) // 当前正在访问第cur个合法状态{x,y}
{if(cur == n * m) {ans++;return;}st[x][y] = true;for(int i = 0; i < 8; ++i) // 每一种方向代表一种方案 {int a = x + dir[i][0];int b = y + dir[i][1];if(a < 0 || a >= n || b < 0 || b >= m) continue;if(st[a][b]) continue;dfs(cur+1,a,b);}st[x][y] = false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int T; cin >> T;while(T--){memset(st, 0, sizeof st);ans = 0;cin >> n >> m >> S.x >> S.y;dfs(1,S.x,S.y);cout << ans << endl;}return 0;
}
四、单词接龙
标签：DFS
思路：这道题就是传入一个单词，然后遍历自己的子串长度，再遍历单词组，查看是否满足要求，如果满足就接上去，然后定义一个全局变量找最大龙的长度。另外开头为一个字母，需要特判一下。
题目描述：
单词接龙是一个与我们经常玩的成语接龙相类似的游戏。现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。输入格式
输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最
后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。输出格式
只需输出以此字母开头的最长的“龙”的长度。数据范围
n≤20，单词随机生成。输入样例：
5
at
touch
cheat
choose
tact
a
输出样例：
23
提示
连成的“龙”为 atoucheatactactouchoose。
示例代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 25, M = N, INF = 0x3f3f3f3f;int n, m;
string str[N], src;
unordered_map<string,int> cnt;
int ans;void dfs(string dragon, bool flag)
{ans = max(ans, (int)dragon.size());for(int len = 1; len <= dragon.size(); ++len){int size1 = dragon.size();if(!flag && len == size1) continue;string t1 = dragon.substr(size1-len);for(int i = 0; i < n; ++i){if(cnt[str[i]] >= 2) continue;int size2 = str[i].size();if(size2 < 1 || len > size2) continue;string t2 = str[i].substr(0,len);if(t1 != t2) continue;cnt[str[i]]++;dfs(dragon+str[i].substr(len),false);cnt[str[i]]--;}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i) cin >> str[i], cnt[str[i]] = 0;cin >> src;dfs(src,true);cout << ans << endl;return 0;
}
五、分成互质组
标签：DFS
思路：首先互质是两个数的最大公约数为 1 1 1 ，互质组就是任意两个数的最大公约数都为 1 1 1 。这道题就是一个简单的暴搜，一个数要么加入到当前的组里去，要么新开一个组存进去。这里说一下写法，第一种就是朴素的 void dfs(int u, int k) ，这里的 u , k u,k u,k 都是从 0 0 0 开始的，当 u = n u = n u=n 时，说明当前所有的数都已经被放到组里去了，说明当前的 k k k 是一种方案。这里的 k k k 就是组数，我们放数的时候是从 0 ∼ k − 1 0\sim k-1 0∼k−1 枚举的，这样也符合一般的习惯，新开的数组编号就为 k k k ，当前的组数就变为了 k + 1 k+1 k+1 。然后迭代加深的参数列表为 void dfs(int u, int k, int depth) 从开始的求最值变为了求是否是可行解，因为本就是从最小的值变过来的，只要可行就是最优解。具体细节见代码。
题目描述：
示例代码1：朴素暴搜
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 15, M = N, INF = 0x3f3f3f3f;int n, m;
int a[N];
vector<int> g[N];
int ans = N;int gcd(int a, int b)
{return b ? gcd(b,a%b) : a;
}bool check(int x, int k)
{for(int i = 0; i < g[k].size(); ++i){if(gcd(x,g[k][i]) > 1) return false;}return true;
}void dfs(int u, int k)
{if(k >= ans) return;if(u == n){ans = k;return;}for(int i = 0; i < k; ++i){if(check(a[u],i)){g[i].push_back(a[u]);dfs(u+1,k);g[i].pop_back();}}g[k].push_back(a[u]);dfs(u+1,k+1);g[k].pop_back();
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i) cin >> a[i];dfs(0,0);cout << ans << endl;return 0;
}
示例代码2：迭代加深
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 15, M = N, INF = 0x3f3f3f3f;int n, m;
int a[N];
vector<int> g[N];int gcd(int a, int b)
{return b ? gcd(b,a%b) : a;
}bool check(int x, int k)
{for(int i = 0; i < g[k].size(); ++i){if(gcd(x,g[k][i]) > 1) return false;}return true;
}bool dfs(int u, int k, int depth)
{if(k > depth) return false;if(u == n) return true;for(int i = 0; i < k; ++i){if(check(a[u],i)){g[i].push_back(a[u]);if(dfs(u+1,k,depth)) return true;g[i].pop_back();}}g[k].push_back(a[u]);if(dfs(u+1,k+1,depth)) return true;g[k].pop_back();return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i) cin >> a[i];int depth = 0;while(!dfs(0,0,depth)) depth++;cout << depth << endl;return 0;
}
六、小猫爬山
标签：搜索、深度优先搜索、DFS
思路：本质上跟上一道题是一模一样，就是 c h e c k check check 函数变了而已。另外这里用到了几个常用的剪枝，首先一般这种重量的都会从大到小去遍历，因为越大放的东西越少，分支就少了。其次就是最优性剪枝和可行性剪枝了，对于一些枚举组的，要用到排除等效冗余，其余的就是正常写法了。
题目描述：
翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。翰翰和达达只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过 W。每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。数据范围
1≤N≤18,1≤Ci≤W≤108
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2
示例代码1：朴素暴力
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 20, M = N, INF = 0x3f3f3f3f;int n, m;
int w[N];
int sum[N];
int ans = N;void dfs(int u, int k)
{if(k >= ans) return; // 最优性剪枝 if(u == n){ans = k;return;}for(int i = 0; i < k; ++i){if((LL)w[u] + sum[i] <= m) // 可行性剪枝{sum[i] += w[u];dfs(u+1,k);sum[i] -= w[u];}}sum[k] += w[u];dfs(u+1,k+1);sum[k] -= w[u];
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < n; ++i) cin >> w[i];sort(w,w+n,greater<int>()); // 优化搜索顺序 dfs(0,0);cout << ans << endl;return 0;
}
示例代码2：迭代加深
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 20, M = N, INF = 0x3f3f3f3f;int n, m;
int w[N];
int sum[N];bool dfs(int u, int k, int depth)
{//这里要判断是否可行，而不是最优 if(k > depth) return false; // 最优性剪枝if(u == n) return true; for(int i = 0; i < k; ++i){if((LL)w[u] + sum[i] <= m) // 可行性剪枝{sum[i] += w[u];if(dfs(u+1,k,depth)) return true;sum[i] -= w[u];}}sum[k] += w[u];if(dfs(u+1,k+1,depth)) return true;sum[k] -= w[u];return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < n; ++i) cin >> w[i];sort(w,w+n,greater<int>()); // 优化搜索顺序 int depth = 0;while(!dfs(0,0,depth)) depth++;cout << depth << endl;return 0;
}
七、数独
标签：搜索、深度优先搜索、DFS
思路：这道题整体上是每次找到一个可以填入数字最少的一个（优化搜索顺序），然后填入继续迭代，直至所有的数都被填满了。这里运用了二进制的思想，把每一列看作一个二进制位，然后用二进制位的思想进行优化，具体细节见代码。
题目描述：
数独 是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰
好出现一次。请编写一个程序填写数独。输入格式
输入包含多组测试用例。每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。您可以假设输入中的每个谜题都只有一个解决方案。文件结尾处为包含单词 end 的单行，表示输入结束。输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
示例代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 9, M = 1 << N, INF = 0x3f3f3f3f;int n, m;
int row[N], col[N], cell[3][3];
int ones[M], mmap[M];
string str;
int cnt;void init()
{cnt = 0;for(int i = 0; i < N; ++i) row[i] = col[i] = (1 << N) - 1;for(int i = 0; i < 3; ++i){for(int j = 0; j < 3; ++j){cell[i][j] = (1 << N) - 1;}}
}void draw(int x, int y, int t, bool is_set)
{if(is_set) str[x*N+y] = t + '1';else str[x*N+y] = '.';int v = 1 << t;if(!is_set) v = -v;row[x] -= v;col[y] -= v;cell[x/3][y/3] -= v;
}int get(int x, int y)
{return row[x] & col[y] & cell[x/3][y/3];
}int lowbit(int x)
{return x & -x;
}bool dfs(int cnt)
{if(!cnt) return true;int minv = 10, x, y;for(int i = 0; i < N; ++i){for(int j = 0; j < N; ++j){if(str[i*N+j] == '.'){int state = get(i,j);if(ones[state] < minv){minv = ones[state];x = i, y = j;}}}}int state = get(x,y);for(int i = state; i; i -= lowbit(i)){int t = mmap[lowbit(i)];draw(x,y,t,true);if(dfs(cnt-1)) return true;draw(x,y,t,false);}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);for(int i = 0; i < N; ++i) mmap[1 << i] = i;for(int i = 0; i < 1 << N; ++i){for(int j = 0; j < N; ++j){ones[i] += i >> j & 1; }} while(cin >> str, str != "end"){init();int cnt = 0;for(int i = 0; i < N; ++i){for(int j = 0; j < N; ++j){if(str[i*N+j] != '.'){int t = str[i*N+j] - '1';draw(i,j,t,true);}else cnt++;}}if(dfs(cnt)) cout << str << endl;}return 0;
}
八、木棒
标签：搜索、DFS、剪枝
思路：这道题是枚举组，因为只有当一组满了，才能去枚举下一组，如果当前组都不能填满，那就是错的。然后这个剪枝的策略也是比较的经典，可以看看。
题目描述：
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。输入格式
输入包含多组数据，每组数据包括两行。第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。数据范围
数据保证每一节木棍的长度均不大于 50。输入样例：
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例：
6
5
示例代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 70, M = N, INF = 0x3f3f3f3f;int n, m;
int w[N];
int len, sum;
bool st[N];bool dfs(int u, int s, int start)
{if(u * len == sum) return true; // 说明前u组已经满了 if(s == len) return dfs(u+1,0,0);for(int i = start; i < n; ++i) // 排除性冗余 {if(!st[i] && (LL)w[i] + s <= len){st[i] = true;if(dfs(u,s+w[i],i+1)) return true;st[i] = false;if(!s || s + w[i] == len) return false; int j = i + 1;while(j < n && w[i] == w[j]) j++;i = j - 1;}}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);while(cin >> n, n){memset(st, 0, sizeof st);len = sum = 0;for(int i = 0; i < n; ++i) {cin >> w[i];sum += w[i];len = max(len, w[i]);}sort(w, w+n, greater<int>()); // 优化搜索顺序 while(true){if(sum % len == 0 && dfs(0,0,0)){cout << len << endl;break;}len++;}}return 0;
}
九、加成序列
标签：搜索、迭代加深
思路：枚举每一个数，每一个数可能的情况，然后进行判断，最后的结果是否可行，然后利用迭代加深的性质找出最小值。一些搜索剪枝已经在代码中给出，更多细节见代码。
题目描述：
满足如下条件的序列 X（序列中元素被标号为 1、2、3…m）被称为“加成序列”：X[1]=1
X[m]=n
X[1]<X[2]<…<X[m−1]<X[m]
对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得 X[k]=X[i]+X[j]。
你的任务是：给定一个整数 n，找出符合上述条件的长度 m 最小的“加成序列”。如果有多个满足要求的答案，只需要找出任意一个可行解。输入格式
输入包含多组测试用例。每组测试用例占据一行，包含一个整数 n。当输入为单行的 0 时，表示输入结束。输出格式
对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。每个输出占一行。数据范围
1≤n≤100
输入样例：
5
7
12
15
77
0
输出样例：
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
示例代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 110, M = N, INF = 0x3f3f3f3f;int n, m;
int path[N];bool dfs(int u, int depth) // 正在选 下标为u的数
{if(u > depth) return false;if(u == depth) return path[u-1] == n;bool st[N] = {0};for(int i = u - 1; i >= 0; --i){for(int j = i; j >= 0; --j) // 排除行冗余 {int s = path[i] + path[j];if(st[s] || s <= path[u-1] || s > n) continue; // 排除性冗余st[s] = true;path[u] = s; if(dfs(u+1,depth)) return true;}}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);while(cin >> n, n){path[0] = 1;int depth = 1;while(!dfs(1,depth)) depth++;for(int i = 0; i < depth; ++i){cout << path[i] << " ";}cout << endl;}return 0;
}
十、排书
标签：搜索、IDA*
思路：首先估价函数就是没排书一次会改变三个状态的正确性，然后最少需要 ⌈ r e s 3 ⌉ \lceil \frac{res}{3}\rceil ⌈3res⌉ ，这个估价函数的设置必须是小于等于真实值的。然后进行迭代加深，根据其性质第一次可行即最优解，然后就是每次操作，进行暴力枚举所有可能的情况。
题目描述：
给定 n 本书，编号为 1∼n。在初始状态下，书是任意排列的。在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。我们的目标状态是把书按照 1∼n 的顺序依次排列。求最少需要多少次操作。输入格式
第一行包含整数 T，表示共有 T 组测试数据。每组数据包含两行，第一行为整数 n，表示书的数量。第二行为 n 个整数，表示 1∼n 的一种任意排列。同行数之间用空格隔开。输出格式
每组数据输出一个最少操作次数。如果最少操作次数大于或等于 5 次，则输出 5 or more。每个结果占一行。数据范围
1≤n≤15
输入样例：
3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10
输出样例：
2
3
5 or more
示例代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 20, M = N, INF = 0x3f3f3f3f;int n, m;
int w[N];int f()
{int res = 0;for(int i = 1; i < n; ++i){if(w[i] != w[i-1] + 1) res++;}return (res + 2) / 3;
}bool dfs(int u, int depth)
{if(u + f() > depth) return false; // 已经完成u次操作if(!f()) return true; for(int len = 1; len <= n; ++len){for(int l = 0; l + len - 1 < n; ++l){int r = l + len - 1;for(int k = r + 1; k < n; ++k) // 移动到k的后面{//把[r+1,k]移动到[l,r], 把[l,r]移动到之后int backup[N]; memcpy(backup, w, sizeof w);int i = l, j = r + 1;for(; j <= k; ++i, ++j) w[i] = backup[j];for(j = l; j <= r; ++i, ++j) w[i] = backup[j];if(dfs(u+1,depth)) return true;memcpy(w, backup, sizeof w);}}}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int T; cin >> T;while(T--){cin >> n;for(int i = 0; i < n; ++i) cin >> w[i];int depth = 0;while(depth < 5 && !dfs(0,depth)) depth++;if(depth >= 5) cout << "5 or more" << endl;else cout << depth << endl;}return 0;
}
这篇关于算法刷题day55：搜索（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
