迭代加深
避免搜索过深 但答案在较浅的位置这种情况的发生
AcWing170. 加成序列
满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：
你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
输入格式
输入包含多组测试用例。
每组测试用例占据一行，包含一个整数n。
当输入为单行的0时，表示输入结束。
输出格式
对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。
每个输出占一行。
数据范围
1 ≤ n ≤ 100
剪枝策略
优化搜索顺序：① 优先枚举较大的数
排除等效冗余：① 某两对数和相等时 只需要选择其中一对
代码
#include<bits/stdc++.h> using namespace std; const int N = 110; int n; int ans[N]; bool dfs(int u, int depth) { if (u > depth)return false; if (ans[u - 1] == n)return true; bool st[N] = { 0 }; for (int i = u - 1; i >= 0; --i) { for (int j = i; j >= 0; --j) { int s = ans[i] + ans[j]; if (st[s] || s > n || s <= ans[u - 1])continue; st[s] = true; ans[u] = s; if (dfs(u + 1, depth))return true; } } return false; } int main() { ans[0] = 1; while (cin >> n, n) { int depth = 1; while (!dfs(1, depth))depth++; for (int i = 0; i < depth; ++i)printf("%d ", ans[i]); cout << endl; } }
双向DFS
AcWing171. 送礼物
达达帮翰翰给女生送礼物，翰翰一共准备了N个礼物，其中第i 个礼物的重量是G [ i]
达达的力气很大，他一次可以搬动重量之和不超过W的任意多个物品。
达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数，分别代表W和N。
以后N行，每行一个正整数表示G[i]。
输出格式
仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。
数据范围
剪枝策略
1.将所有物品按重量从大到小排序
2.先将前k 件物品能凑出的重量打表，然后排序判重
3.搜索剩下的N − K 件物品的选择方式 并从表中二分出不超过W的最大值
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 50; int n, m; int w[N], weights[1 << 25]; int k, cnt = 1, res; void dfs1(int u, int s) { if (u == k) { weights[cnt++] = s; return; } dfs1(u + 1, s); if ((LL)s + w[u] <= m)dfs1(u + 1, s + w[u]); } void dfs2(int u, int s) { if (u == n) { int l = 0, r = n; while (l < r) { int mid = l + r + 1 >> 1; if (weights[mid] <= m - s)l = mid; else r = mid - 1; } res = max(res, weights[l] + s); return; } dfs2(u + 1, s); if ((LL)s + w[u] <= m)dfs2(u + 1, s + w[u]); } int main() { cin >> m >> n; for(int i = 1;i <= n;++i){ scanf("%d", &w[i]); } sort(w, w + n); reverse(w, w + n); int k = n / 2 + 2; dfs1(1, 0); cnt = unique(weights, weights + cnt) - weights; dfs2(k + 1, 0); cout << res << endl; return 0; }
IDA-star
启发式搜索 + 迭代加深
如果估价函数(需要再搜的最小层数) + 当前层数 > 当前迭代加深的层数 在当前迭代肯定无解
迭代扩大搜索的层数 直到最终找到答案 或者无解
AcWing180. 排书
给定n本书，编号为1-n。
在初始状态下，书是任意排列的。
在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。
我们的目标状态是把书按照1-n的顺序依次排列。
求最少需要多少次操作。
输入格式
第一行包含整数T ，表示共有T 组测试数据。
每组数据包含两行，第一行为整数n，表示书的数量。
第二行为n nn个整数，表示1 − n 的一种任意排列。
同行数之间用空格隔开。
输出格式
每组数据输出一个最少操作次数。
如果最少操作次数大于或等于5次，则输出”5 or more”。
每个结果占一行。
数据范围
1 ≤ n ≤ 15
思路
枚举移动串的长度 和插入的位置 一层一层地搜
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 15; int n; int a[N], w[5][N]; int f() { int cnt = 0; for (int i = 0; i + 1 < n; ++i) if (a[i + 1] != a[i] + 1) ++cnt; return (cnt + 2) / 3; } bool dfs(int depth, int max_depth) { if (depth + f() > max_depth)return false; if (f() == 0)return true; for (int len = 1; len <= n; ++len) { //枚举当前移动的长度 for (int l = 0; l + len - 1 < n; ++l) { //枚举截取的起点 int r = l + len - 1; //计算终点 // 把 l 到 r 这一段放到k的后面去 for (int k = r + 1; k < n; ++k) {// 枚举应该插在哪个地方 避免重复 每次都往后放 memcpy(w[depth], a, sizeof a); int y = l; for (int x = r + 1; x <= k; ++x,++y)a[y] = w[depth][x]; for (int x = l; x <= r; ++x, ++y)a[y] = w[depth][x]; if (dfs(depth + 1, max_depth))return true; memcpy(a, w[depth], sizeof a); } } } return false; } int main() { int t; cin >> t; while (t--) { cin >> n; for (int i = 0; i < n; ++i)scanf("%d", &a[i]); int depth = 0; while (depth < 5 && !dfs(0, depth))depth++; if (depth >= 5)puts("5 or more"); else cout << depth << endl; } }
AcWing181. 回转游戏
如下图所示，有一个“#”形的棋盘，上面有1,2,3三种数字各8个。
给定8种操作，分别为图中的A~H。
这些操作会按照图中字母和箭头所指明的方向，把一条长为8的序列循环移动1个单位。
例如下图最左边的“#”形棋盘执行操作A后，会变为下图中间的“#”形棋盘，再执行操作C后会变成下图最右边的“#”形棋盘。
给定一个初始状态，请使用最少的操作次数，使“#”形棋盘最中间的8个格子里的数字相同。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含24个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。
输入样例中的第一个测试用例，对应上图最左边棋盘的初始状态。
当输入只包含一个“0”的行时，表示输入终止。
输出格式
每个测试用例输出占两行。
第一行包含所有移动步骤，每步移动用大写字母“A~G”中的一个表示，字母之间没有空格，如果不需要移动则输出“No moves needed”。
第二行包含一个整数，表示移动完成后，中间8个格子里的数字。
如果有多种方案，则输出字典序最小的解决方案。
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 24; int op[8][7] = { //图表顺序 {0,2,6,11,15,20,22}, {1,3,8,12,17,21,23}, {10,9,8,7,6,5,4}, {19,18,17,16,15,14,13}, {23,21,17,12,8,3,1}, {22,20,15,11,6,2,0}, {13,14,15,16,17,18,19}, {4,5,6,7,8,9,10}, }; int opposite[8] = { 5,4,7,6,1,0,3,2 }; //每个操作对应的逆操作 int center[8] = { 6,7,8,11,12,15,16,17 }; int q[N]; int path[100]; int f() { int sum[4] = { 0 }; for (int i = 0; i < 8; ++i) { sum[q[center[i]]]++; } int s = 0; for (int i = 1; i <= 3; ++i) { s = max(s, sum[i]); } return 8 - s; } void operate(int x) { int s = q[op[x][0]]; for (int i = 0; i < 6; ++i) { q[op[x][i]] = q[op[x][i + 1]]; } q[op[x][6]] = s; } bool dfs(int depth, int max_depth,int last) { if (depth + f() > max_depth)return false; if (!f())return true; for (int i = 0; i < 8; ++i) { if (opposite[i] != last) { operate(i); path[depth] = i; if (dfs(depth + 1, max_depth,i))return true; operate(opposite[i]); } } return false; } int main() { while (cin >> q[0], q[0]) { for (int i = 1; i < 24; ++i)scanf("%d", &q[i]); int depth = 0; while (!dfs(0, depth,-1))depth++; if (!depth)printf("No moves needed"); else { for (int i = 0; i < depth; ++i)printf("%c", path[i] + 'A'); } printf("\n%d\n", q[6]); } }
