Core Logic and Mathematical Principles
The essence of search is traversing the state space tree. Faced with the exponential growth of the state space, the underlying logic of pruning is to terminate invalid branches early, theoretically reducing the search complexity from $O(k^N)$ to a practically feasible scale.
- Feasibility Pruning: Check constraint conditions at the current node. Once it is found that the current path can no longer satisfy legality (e.g., out of bounds, resources exhausted), backtrack immediately. Its mathematical expression is: let the current state be $S$, and the constraint function be $g(S)$; if $g(S) = \text{False}$, cut off the entire subtree rooted at $S$.
- Optimality Pruning: Maintain a global optimal solution $ans$. During the search process, if the current cost $val(S)$ plus the estimated minimum cost $h(S)$ is already greater than or equal to $ans$, this branch cannot yield a better solution, and it terminates directly. The mathematical criterion is: $val(S) + h(S) \ge ans$.
- Bound Pruning: For permutation or combination searches, precisely calculate the legal value range $[L, R]$ of the current layer variable $x_i$ through preprocessing or mathematical derivation. By strictly limiting the enumeration boundaries of the
forloop, eliminate invalid branch derivations.
State Design and Algorithm Derivation
Taking the classic problem of "Birthday Cake" (NOI1999 / Luogu P1731) as an example. The problem requires building a cake with a total volume of $N$ in $M$ layers, with radius $R$ and height $H$ strictly decreasing from bottom to top, seeking to minimize the surface area.
1. State Design
The search state is determined by the current layer number, current volume, current surface area, and the radius and height of the previous layer. Define the DFS function state: dfs(dep, v, s, last_r, last_h). Here, dep is the current layer being searched (from bottom to top, with the bottom being layer $M$ and the top being layer $1$).
2. Bound Derivation
For the $i$-th layer, the volume and height must be greater than or equal to the minimum volume and height of all layers above it.
- Lower bound: $R_i \ge i$, $H_i \ge i$.
- Upper bound: Determined by the remaining volume and height constraints.
$$R_i \le \min\left(\lfloor \sqrt{N - v} \rfloor, last_r - 1\right)$$
$$H_i \le \min\left(\lfloor \frac{N - v}{R_i^2} \rfloor, last_h - 1\right)$$
3. Pruning Strategy Derivation
- Feasibility Pruning: Preprocess the minimum volume and minimum lateral area sums from layer $1$ to layer $i$, denoting them as $minV[i]$ and $minS[i]$. If $v + minV[dep] > N$, backtrack directly.
- Optimality Pruning 1: If the current surface area plus the minimum lateral area of the top layer exceeds the global optimum, i.e., $s + minS[dep] \ge ans$, backtrack.
- Optimality Pruning 2 (Mathematical Derivation Scaling): The remaining volume $N - v = \sum_{j=1}^{dep} R_j^2 H_j$. The remaining lateral area $\sum_{j=1}^{dep} 2 R_j H_j = \frac{2}{R_{dep+1}} \sum_{j=1}^{dep} R_j H_j R_{dep+1} > \frac{2}{last_r} \sum_{j=1}^{dep} R_j^2 H_j = \frac{2(N - v)}{last_r}$. This leads to the powerful optimality pruning inequality:
$$s + \frac{2(N - v)}{last_r} \ge ans \implies \text{Backtrack}$$
C++ Standard Source Code
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
int N, M;
int ans = 2e9;
int min_v[25], min_s[25];
// State: dep(current layer), v(accumulated volume), s(accumulated surface area), r(previous layer radius), h(previous layer height)
void dfs(int dep, int v, int s, int r, int h) {
if (dep == 0) {
if (v == N) {
ans = std::min(ans, s);
}
return;
}
// Feasibility Pruning: Current volume + minimum volume of the top layer > target volume
if (v + min_v[dep] > N) return;
// Optimality Pruning 1: Current surface area + minimum lateral area of the top layer >= known optimal solution
if (s + min_s[dep] >= ans) return;
// Optimality Pruning 2: Use mathematical inequality to estimate the lower bound of future costs
if (s + 2 * (N - v) / r >= ans) return;
// Bound Pruning: Enumerate from bottom to top, prioritizing larger sizes (optimizing search order)
int max_r = std::min(static_cast<int>(std::sqrt(N - v)), r - 1);
for (int cur_r = max_r; cur_r >= dep; --cur_r) {
if (dep == M) {
s = cur_r * cur_r; // The base area of the cake is counted once at layer M
}
int max_h = std::min((N - v) / (cur_r * cur_r), h - 1);
for (int cur_h = max_h; cur_h >= dep; --cur_h) {
// Critical pitfall: Ensure that the base area is only included in special cases or at the first layer when recursively passing s; here only accumulate lateral area
dfs(dep - 1, v + cur_r * cur_r * cur_h, s + 2 * cur_r * cur_h, cur_r, cur_h);
}
}
}
int main() {
// Improve I/O efficiency to prevent timeout with large data volumes
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
if (!(std::cin >> N >> M)) return 0;
// Preprocess prefix sums to provide boundary data for pruning
for (int i = 1; i <= M; ++i) {
min_v[i] = min_v[i - 1] + i * i * i;
min_s[i] = min_s[i - 1] + 2 * i * i;
}
// Initial upper limit setting: Theoretical maximum radius and height cannot exceed N
dfs(M, 0, 0, N, N);
if (ans == 2e9) {
std::cout << 0 << "\n";
} else {
std::cout << ans << "\n";
}
return 0;
}NOIP Practical Pitfall Guide
- Search Order Reversal Leading to Pruning Failure
In the absence of dependency relationships, prioritize enumerating decisions with "fewer branches" or "higher costs". For example, in combinatorial optimization or pruning problems, enumerating the
forloop from large to small (frommax_rtodep) allows deeper states to approach the global optimal solution $ans$ earlier, thereby increasing the likelihood of triggering subsequent pruning $s + min_s[dep] >= ans$. Enumerating from small to large can lead to severe left-side expansion of the search tree. - Integer Truncation and Estimation Function Overflow
When performing mathematical scaling for optimality pruning, expressions like
s + 2 * (N - v) / rmay cause downward rounding if integer division is used directly, leading to an underestimated lower bound. In extreme cases, if it is just at the edge of the optimal solution, this error may lead to incorrect pruning (killing the correct solution). Additionally, when calculating cubes and squares, if the range of $N$ increases (as in some variant problems), failure to convert tolong longmay cause data overflow, resulting in feasibility pruning failure and triggering infinite loops.
Classic NOIP/Luogu Real Questions
1. Luogu P1120 Little Sticks
- Problem Description: Several equal-length sticks are randomly cut into $N$ small sticks of length not exceeding 50. Given the lengths of the cut sticks, find the minimum possible length of the original stick.
- Essence of the Problem: Multi-set equal-sum subset partition problem.
- Core Solving Idea:
- Bound Pruning: The length of the original stick must be within the range $[max_len, sum_len]$, and must be divisible by $sum_len$.
- Optimizing Search Order: Sort the lengths of small sticks from large to small, and first assemble larger sticks.
- Feasibility Pruning (Deduplication): If the current stick attempt fails, skip all subsequent sticks of the same length; if it fails at the beginning of assembling a new stick or at the last stick when finishing one, directly determine that the current original length is invalid, rejecting inefficient backtracking.
2. Luogu P1434 Skiing
- Problem Description: Given a two-dimensional grid, each cell has its height. You can only slide from high to low in four directions, and find the length of the longest sliding track.
- Essence of the Problem: Longest path search on a DAG (Directed Acyclic Graph).
- Core Solving Idea:
- Memoization Pruning: The ultimate form of feasibility and repetitive state pruning. Define $f[x][y]$ as the longest path starting from $(x,y)$.
- Logical Pruning: In the DFS process, if it is found that $f[x][y]$ has already been computed, return its value directly, reducing the exponential search tree to a linear graph traversal of $O(N \times M)$ and preventing repeated searches of the same sub-state.