剪枝就是排除搜索树中不必要的分支
比如，如果知道往某个支路走答案必定（或者已经）不如当前最优解，那么就可以跳过这个支路
同样，为了可以剪掉更多枝，可以优先往期望较优的分支走
可以对当前状态“估价”，例如当前状态到最终状态至少要 \(x\) 步，而当前已经走过的步数再加上 \(x\) 大于等于当前的最优解步数，则直接回溯
可以定义一个递归函数，例如 dfs(p, low)，代表为位置 p，从不小于 low 的数中选择一个。
p 表示当前正在填充组合中的哪个位置，假设索引范围是 0 到 m - 1。low 表示为当前位置 p 选择数字时的起始搜索范围，这是确保顺序的关键。通过强制下一次选择的数字 i 必须大于或等于 low，并且在递归到下一层时将 low 更新为 i + 1，保证了组合中的数字是严格递增的。递归出口：当递归函数被调用且 p == m 时，说明已经成功地为组合的所有 m 个位置都选择了数字。此时，一个完整的组合已经形成，将其打印出来，然后返回，结束这一条搜索路径。
递归过程：对于当前的位置 p，需要从 low 到 n 的范围内选择一个数 i，使用一个循环来遍历所有的选择。
在实现基本逻辑的基础上，还可以进行剪枝优化。如果剩下的数字数量已经少于还需要选择的数量，那么无论如何也无法凑成一个完整的 m 元组合了。此时，可以直接 return，终止这条无效的搜索路径，从而提高效率。
#include <cstdio>
int n, m, a[25];
// 深度优先搜索函数，用于生成组合
// p: 当前正在处理的位置的索引 (从0到m-1)
// low: 当前选择的起始数字，确保新选择的数比之前的大
void dfs(int p, int low) {
// 剪枝优化：如果剩下可选的数字数量，已经不足以填满组合，则提前返回
if (p + (n - low + 1) < m) {
return;
}
// 递归出口：当组合中的数字数量达到m时，打印该组合
if (p == m) {
for (int i = 0; i < m; i++) {
printf("%d ", a[i]);
}
printf("\n");
return;
}
// 从low到n循环，尝试将每个数字加入组合
for (int i = low; i <= n; i++) {
a[p] = i; // 选择当前数字i
dfs(p + 1, i + 1); // 递归搜索下一个数字，起始数字为 i+1
}
}
int main()
{
scanf("%d%d", &n, &m);
dfs(0, 1); // 从数字1开始进行深度优先搜索
return 0;
}
可以使用深度优先搜索算法解决本题，在搜索的过程中，可以尝试依次把每一只小猫分配到一辆已经租用的缆车上，或者新租一辆缆车安置这只小猫。于是，需要关心的状态有：已经运送的小猫有多少只，已经租用的缆车有多少辆，每辆缆车上当前搭载的小猫重量之和。
编写函数 \(\text{dfs}(u,k)\) 处理第 \(u\) 只小猫的分配过程，并且目前已经租用了 \(k\) 辆缆车。对于已经租用的缆车的当前搭载量，可以使用一个数组来记录。
为了让搜索过程更加高效，可以加入一个很显然的优化：如果在搜索的任何时刻发现 \(k\) 已经大于或等于已经搜到的答案，那么当前分支就可以立即回溯了。另外，重量较大的小猫显然比重量较轻的小猫更“难”运送，还可以在整个搜索前把小猫按照重量递减排序，优先搜索重量较大的小猫，减少搜索过程中“分支”的数量。
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
int n, w, c[18], ans;
int car[18]; // 存储每辆缆车当前已装载的重量
/**
* DFS 搜索函数
* @param u 当前处理到第 u 只猫
* @param k 当前已经使用了 k 辆缆车
*/
void dfs(int u, int k) {
// 最优性剪枝
if (k >= ans) return;
// 所有猫都安排好了
if (u == n) {
ans = k;
return;
}
// 尝试放入已有的缆车
for (int i = 0; i < k; i++) {
if (car[i] + c[u] <= w) {
car[i] += c[u];
dfs(u + 1, k);
car[i] -= c[u]; // 回溯
}
}
// 尝试新开一辆缆车
car[k] = c[u];
dfs(u + 1, k + 1);
car[k] = 0;
}
int main()
{
scanf("%d%d", &n, &w);
for (int i = 0; i < n; i++) {
scanf("%d", &c[i]);
}
// 优化：按重量从大到小排序，利于剪枝
sort(c, c + n, greater<int>());
ans = n; // 最坏情况是每只猫一辆车
dfs(0, 0);
printf("%d\n", ans);
return 0;
}
对于每一枚导弹，可以选择的决策包括：将其放入某个已有的上升序列；将其放入某个已有的下降序列；如果无法放入已有序列，则必须新开一个序列。
通过 DFS 搜索全局最优解，在 DFS 枚举每个导弹属于“上升”还是“下降”组时，内部可以利用贪心思想减少分支：
在搜索过程中，如果当前开辟的系统总数已经大于或等于当前记录的最小答案，则该分支不可能产生最好的结果，直接回溯。
#include <cstdio>
#include <algorithm>
using namespace std;
int n, h[50], ans;
int up[50], down[50]; // 分别记录每个上升系统和下降系统的末尾高度
/**
* DFS 搜索
* @param u 当前处理第 u 个导弹
* @param su 当前已有的上升系统数量
* @param sd 当前已有的下降系统数量
*/
void dfs(int u, int su, int sd) {
// 剪枝：如果当前系统总数已经达到或超过当前最优解，停止搜索
if (su + sd >= ans) return;
// 所有导弹处理完毕
if (u == n) {
ans = su + sd;
return;
}
// 情况 1：将当前导弹放入上升子序列中
int k = 0;
while (k < su && up[k] >= h[u]) k++; // 找到第一个末尾小于当前高度的系统
if (k < su) {
int t = up[k];
up[k] = h[u];
dfs(u + 1, su, sd);
up[k] = t; // 回溯
} else {
up[su] = h[u];
dfs(u + 1, su + 1, sd);
// 新开辟系统回溯时无需还原内容，只需控制计数
}
// 情况 2：将当前导弹放入下降子序列中
k = 0;
while (k < sd && down[k] <= h[u]) k++; // 找到第一个末尾大于当前高度的系统
if (k < sd) {
int t = down[k];
down[k] = h[u];
dfs(u + 1, su, sd);
down[k] = t; // 回溯
} else {
down[sd] = h[u];
dfs(u + 1, su, sd + 1);
}
}
int main()
{
// 循环处理多组测试数据
while (true) {
scanf("%d", &n);
if (n == 0) break;
for (int i = 0; i < n; i++) scanf("%d", &h[i]);
ans = n; // 初始化最大可能需要的系统数为 n
dfs(0, 0, 0);
printf("%d\n", ans);
}
return 0;
}
搜索框架：从下往上搜索，枚举每层的半径和高度作为分支。
搜索面对的状态有：正在搜索第 \(u\) 层，当前外表面面积 \(s\)，当前体积 \(v\)，第 \(u+1\) 层的高度 \(h'\) 和半径 \(r'\)。
整个蛋糕的“上表面”面积之和等于最底层的圆面积，可以在第 \(M\) 层直接累加到 \(s\) 中。这样在第 \(M-1\) 层往上的搜索中，只需要计算侧面积。
剪枝：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m, minv[20], mins[20], ans;
/**
* DFS 搜索函数
* @param u 当前正在搜索第几层（从下往上，第 m 层到底层）
* @param v 当前已用的体积
* @param s 当前已有的表面积
* @param lr 上一层的半径
* @param lh 上一层的高度
*/
void dfs(int u, int v, int s, int lr, int lh) {
// 已经处理完所有层
if (u == 0) {
if (v == n) ans = min(ans, s);
return;
}
// 剪枝 1：可行性剪枝 - 剩余体积无法满足后续层数的最小需求
if (v + minv[u] > n) return;
// 剪枝 2：最优性剪枝 - 当前面积 + 后续最小侧面积已超当前最优
if (s + mins[u] >= ans) return;
// 剪枝 3：最优性剪枝 - 数学推导，当前面积 + 剩余体积估算的最小面积已超当前最优
if (s + 2.0 * (n - v) / lr >= ans) return;
// 枚举当前层的半径 r 和高度 h
// r 必须小于上一层半径，且至少为当前层数 u
for (int r = min(lr - 1, (int)(sqrt(n - v))); r >= u; r--) {
if (u == m) s = r * r; // 底层需要加上顶面面积（等于底层半径的平方）
// h 必须小于上一层高度，且至少为当前层数 u
int maxh = min(lh - 1, (n - v) / (r * r));
for (int h = maxh; h >= u; h--) {
dfs(u - 1, v + r * r * h, s + 2 * r * h, r, h);
}
}
}
int main()
{
ans = 1e9;
scanf("%d%d", &n, &m);
// 预处理前 i 层的最小体积和最小侧面积
for (int i = 1; i <= m; i++) {
minv[i] = minv[i - 1] + i * i * i;
mins[i] = mins[i - 1] + 2 * i * i;
}
dfs(m, 0, 0, (int)(sqrt(n)) + 1, n + 1);
if (ans == 1e9) printf("0\n");
else printf("%d\n", ans);
return 0;
}
实际上，搜索算法面对的状态可以看作一个多元组，其中每一元都是问题状态空间中的一个维度。例如本题中，层数 \(u\)、表面积 \(s\)、体积 \(v\)、下层的高度和半径就构成状态空间中的五个维度，其中每一项发生变化，都会移动到状态空间中的另一个“点”。
搜索过程中的剪枝，其实就是针对每个“维度”与该维度的边界条件，加以缩放、推导，得出一个相应的不等式，来减少搜索分支的扩张。
为了进一步提高剪枝的效果，除了当前花费的“代价”之外，还可以对未来至少需要花费的代价进行预算，这样更容易接近每个维度的上下界，本题中的上面层最小体积、最小侧面积就是这个思想。通过表面积与体积之间的关系，对不等式进行缩放得到的式子也是对上面层侧面积的一个估计。这说明在一般的剪枝不足以应对问题的时候，也可以结合各维度之间的联系得到更加精准的剪枝。
由于线路较少，但时间点和组合情况较多，直接对每一个时间点搜索会非常慢，因此采用预处理所有合法线路再进行 DFS 的策略。
遍历所有可能的起始时间 \(S \in [0, 29]\) 和间隔 \(D \in [S+1, 59-S]\)：
将预处理出的线路按停靠次数降序排序，优先尝试能“消掉”更多公交记录的线路，可以更快地减少剩余公交总数，从而更早地触发剪枝条件，极大提高搜索效率。
DFS 过程中如果不剪枝会由于分支过多而超时，可以实现以下剪枝：
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
// 定义公交线路结构体
struct Route {
int start, step, num; // 起始时间，间隔分钟，该小时内停靠总次数
};
int bus[60], cnt, ans;
vector<Route> r;
// 排序规则：按停靠次数从大到小排序
// 优先尝试覆盖能力强的线路，可以更快地进入较深的搜索层级并触发剪枝
bool cmp(Route a, Route b) {
return a.num > b.num;
}
// 检查在当前剩余的公交记录中，是否能完整提取出某条线路
bool check(int s, int d) {
for (int t = s; t < 60; t += d) {
if (bus[t] == 0) return false;
}
return true;
}
/**
* 深度优先搜索
* @param idx 当前尝试的线路在预处理线路中的索引
* @param cur 当前已选择的线路数量
* @param left 剩余未被覆盖的公交到站记录总数
*/
void dfs(int idx, int cur, int left) {
// 成功覆盖所有记录
if (left == 0) {
ans = min(ans, cur);
return;
}
// 最优性剪枝：当前选中的线路数已经达到或超过已知最优解
if (cur >= ans) return;
for (int i = idx; i < cnt; i++) {
// 可行性剪枝：
// (当前已选线路) + (剩余记录数 / 当前线路单条覆盖数)
// 如果这个估算值已经超过了已知最优解 ans，则该分支不可能产生更优解
if (cur + left / r[i].num >= ans) continue;
if (check(r[i].start, r[i].step)) {
// 尝试选择该线路：更新记录数组
for (int t = r[i].start; t < 60; t += r[i].step) bus[t]--;
// 注意：传入 i 而非 i+1，因为相同的线路(start, step)可能存在多条
dfs(i, cur + 1, left - r[i].num);
// 回溯：恢复记录数组
for (int t = r[i].start; t < 60; t += r[i].step) bus[t]++;
}
}
}
int main()
{
int n; scanf("%d", &n);
for (int i = 0; i < n; i++) {
int t; scanf("%d", &t);
bus[t]++; // 记录每个时间点到站的公交数量
}
// 1. 预处理所有可能的合法线路
// 起始时间 s 必须在 [0, d-1] 范围内，否则该线路在更早时间就会有记录
cnt = 0;
for (int s = 0; s < 30; s++) {
for (int d = s + 1; s + d < 60; d++) {
if (check(s, d)) {
Route rt = {s, d, (59 - s) / d + 1};
r.push_back(rt);
cnt++;
}
}
}
// 2. 按覆盖效率降序排序，这是搜索优化的关键
sort(r.begin(), r.end(), cmp);
ans = 18;
// 3. 开始搜索
dfs(0, 0, n);
printf("%d\n", ans);
return 0;
}
本题相比于 P10481 [SEERC 2005] Sudoku 性能要求更高。
考虑人类来玩数独，往往是先填上“已经能够唯一确定的位置”，然后从那些填得比较满、选项比较少的位置实施突破。所以，在搜索算法中，也应该采取类似的策略：在每个状态下，从所有未填的位置里选择“能填的合法数字”最少的位置，考虑该位置上填什么树，作为搜索的分支，而不是任意找出一个位置。
还可以使用位运算辅助优化“对数独各个位置所填数字的记录”以及“可填性的检查与统计”。
& 运算，就可以得到该位置能填哪些数，用 lowbit 运算就可以把能填的数字取出。#include <cstdio>
// ones: 记录状态中1的个数；val: 记录2的幂对应的数值
// row[i], col[j], box[k] 分别存储行、列、宫格的可用数字状态
// 位运算：第 x 位为 1 表示数字 x+1 可用
int val[512], ones[512], row[9], col[9], box[9], board[9][9];
char input[82];
// 获取 (r, c) 所在的宫格索引
int get(int r, int c) {
return r / 3 * 3 + c / 3;
}
// 修改状态（填入或擦除）
void flip(int r, int c, int num) {
int val = 1 << num;
row[r] ^= val;
col[c] ^= val;
box[get(r, c)] ^= val;
}
// 获取 (r, c) 处所有可用的数字位掩码
int possible(int r, int c) {
return row[r] & col[c] & box[get(r, c)];
}
int lowbit(int x) {
return x & -x;
}
bool dfs(int cnt) {
if (cnt == 0) return true;
// 寻找备选数字最少的格子进行尝试
int choices = 10, r = 0, c = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) {
int p = possible(i, j);
if (ones[p] < choices) {
choices = ones[p];
r = i; c = j;
}
}
}
}
if (choices == 0) return false; // 剪枝：当前格无数字可选
int p = possible(r, c);
for (int i = p; i > 0; i -= lowbit(i)) {
int num = val[lowbit(i)];
board[r][c] = num + 1;
flip(r, c, num);
if (dfs(cnt - 1)) {
return true;
}
// 回溯
flip(r, c, num);
board[r][c] = 0;
}
return false;
}
int main()
{
// 预处理
for (int i = 0; i < 9; i++) {
val[1 << i] = i;
}
for (int i = 0; i < 512; i++) {
for (int j = i; j > 0; j -= lowbit(j)) {
ones[i]++;
}
}
while (true) {
scanf("%s", input);
if (input[0] == 'e') break;
// 初始化状态：所有数字均可用（511 即二进制 9 个 1）
for (int i = 0; i < 9; i++) {
row[i] = col[i] = box[i] = 511;
}
int cnt = 0;
for (int i = 0; i < 81; i++) {
int r = i / 9, c = i % 9;
if (input[i] == '.') {
board[r][c] = 0;
cnt++;
} else {
int num = input[i] - '1';
board[r][c] = num + 1;
flip(r, c, num);
}
}
if (dfs(cnt)) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%d", board[i][j]);
}
}
printf("\n");
}
}
return 0;
}
同 P10482 Sudoku 2，区别是多了一个计分规则，以及不是只求一组合法解，而是找到得分最高的合法解。
#include <cstdio>
#include <algorithm>
using namespace std;
int ones[1 << 9], num[1 << 9], b[9][9], row[9], col[9], box[3][3], ans;
// 标记位置并更新状态
void flip(int r, int c, int v) {
int bit = 1 << (v - 1);
row[r] ^= bit;
col[c] ^= bit;
box[r / 3][c / 3] ^= bit;
}
// 获取分值权重
int weight(int r, int c) {
if (r == 4 && c == 4) return 10;
if (r >= 3 && r <= 5 && c >= 3 && c <= 5) return 9;
if (r >= 2 && r <= 6 && c >= 2 && c <= 6) return 8;
if (r >= 1 && r <= 7 && c >= 1 && c <= 7) return 7;
return 6;
}
// 获取可选数字的掩码
int get(int r, int c) {
return ((1 << 9) - 1) & ~row[r] & ~col[c] & ~box[r / 3][c / 3];
}
void dfs(int cnt, int score) {
if (cnt == 0) {
ans = max(ans, score);
return;
}
// 找到可选数字最少的格子
int choices = 10, r = 0, c = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (b[i][j] == 0) {
int mask = get(i, j);
if (ones[mask] < choices) {
choices = ones[mask];
r = i; c = j;
}
}
}
}
if (choices == 0) return;
int mask = get(r, c);
for (int i = mask; i > 0; i -= (i & -i)) {
int bit = i & -i;
int val = num[bit] + 1;
b[r][c] = val;
flip(r, c, val);
dfs(cnt - 1, score + val * weight(r, c));
flip(r, c, val); // 回溯
b[r][c] = 0;
}
}
int main()
{
// 预处理位运算辅助工具
for (int i = 0; i < 9; i++) num[1 << i] = i;
for (int i = 0; i < (1 << 9); i++) {
for (int j = i; j > 0; j -= (j & -j)) ones[i]++;
}
int cnt = 0, score = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
scanf("%d", &b[i][j]);
if (b[i][j] != 0) {
int val = b[i][j];
flip(i, j, val);
score += val * weight(i, j);
} else {
cnt++;
}
}
}
ans = -1;
dfs(cnt, score);
printf("%d\n", ans);
return 0;
}
搜索的效率取决于剪枝发生的早晚，为了尽快利用竖式的每列约束，可以采取这样的顺序：从竖式的最低位开始向高位扫描，记录字母出现的先后顺序，存入数组，DFS 过程中按照这个数组的顺序为字母分配数字。
在 DFS 的每一步，从右往左检查每一列：设当前列的字母为 \(A,B,C\)，进位为 \(c\)。如果三个字母都已确定：
另外，在检查完整的竖式计算时，当计算完毕后最高位的进位必须为 \(0\)。
#include <cstdio>
char s[3][27];
bool vis[26];
bool used[26]; // 数字是否已被占用
int n;
int order[26]; // 搜索顺序
int ans[26]; // 字母对应的数字，-1 表示未确定
// 剪枝：利用竖式每列的等式关系
bool fail() {
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int a = ans[s[0][i] - 'A'];
int b = ans[s[1][i] - 'A'];
int c = ans[s[2][i] - 'A'];
if (a != -1 && b != -1 && c != -1) {
if (carry != -1) {
if ((a + b + carry) % n != c) return true;
carry = (a + b + carry) / n;
} else {
if ((a + b) % n != c && (a + b + 1) % n != c) return true;
}
} else {
carry = -1;
}
}
return false;
}
bool dfs(int u) {
if (u == n) {
// 最终检查：从低位到高位模拟一遍
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int a = ans[s[0][i] - 'A'];
int b = ans[s[1][i] - 'A'];
int c = ans[s[2][i] - 'A'];
if ((a + b + carry) % n != c) return false;
carry = (a + b + carry) / n;
}
return carry == 0;
}
// 剪枝：每次填数前检查现有列是否矛盾
if (fail()) return false;
int idx = order[u];
for (int i = 0; i < n; i++) {
if (!used[i]) {
ans[idx] = i;
used[i] = true;
if (dfs(u + 1)) return true;
used[i] = false;
ans[idx] = -1;
}
}
return false;
}
int main()
{
scanf("%d%s%s%s", &n, s[0], s[1], s[2]);
// 预处理搜索顺序：从右往左出现的字母优先
int cnt = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 3; j++) {
int c = s[j][i] - 'A';
if (!vis[c]) {
vis[c] = true;
order[cnt++] = c;
}
}
}
for (int i = 0; i < 26; i++) ans[i] = -1;
dfs(0);
for (int i = 0; i < n; i++) printf("%d ", ans[i]);
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。