Core Logic and Mathematical Principles
The essence of circular dynamic programming is to handle the end-to-end connectivity of topological structures. In a normal linear sequence, positions $1$ and $N$ are disconnected boundaries; however, in a circular structure, there exists an equivalent directed edge between positions $1$ and $N$, causing the state space to be geometrically closed.
For handling circular topologies, there are two mainstream hardcore dimensionality reduction mapping techniques:
-
Breaking the Circle into a Chain (Doubling Method):
- Geometric Mapping: Duplicate the original circular sequence of length $M$ and append it to the end of the original sequence, forming a linear sequence of length $2M$: $A[1 \text{ to } 2M]$.
- Logical Equivalence: Any continuous segment of length $M$ in the original circular structure can uniquely correspond to an interval $[l, l + M - 1]$ in the doubled linear sequence (where $1 \text{ ≤ } l \text{ ≤ } M$).
- Applicable Scenarios: Models such as interval DP and sliding window that require explicit enumeration of all possible continuous sub-intervals on the circle.
-
Converting Boundary to Multiple DP (Boundary Fixing):
- Geometric Mapping: Explicitly cut the circular edge between positions $1$ and $M$, degenerating it into a linear structure. To forcibly close the end-to-end constraints, multiple independent linear DPs must be performed by "enforcing boundary conditions".
- Logical Equivalence: For constraints on adjacent positions (e.g., "two adjacent positions cannot be selected simultaneously"), either position $1$ is not selected (in which case the selection of position $M$ is irrelevant), or position $1$ must be selected (in which case position $M$ cannot be selected). These two boundary conditions exhaustively enumerate all valid topological states connected end-to-end.
- Applicable Scenarios: Tree DP and linear sequence selection problems (e.g., maximum non-adjacent subset in a circle).
State Design and Algorithm Derivation
Taking the classic examples of "Circular Stone Merging" and "Circular Robbery (Maximum Non-Adjacent Subset)" as examples, we break down the state derivation.
1. Circular Interval DP (Breaking the Circle into a Chain)
- State Design: Let $f[l][r]$ represent the minimum cost of merging the interval $[l, r]$ in the doubled sequence.
- Transition Equation:
$$f[l][r] = \min_{l \text{ ≤ } k < r} \bigg\{ f[l][k] + f[k+1][r] \bigg\} + (S[r] - S[l-1])$$
where the prefix sum array $S$ must be preprocessed to the boundary of $2M$.
- Target Answer:
$$\text{Ans} = \min_{1 \text{ ≤ } l \text{ ≤ } M} \bigg\{ f[l][l + M - 1] \bigg\}$$
2. Circular State Compression (Two Times DP Boundary Control)
Assuming the sequence length is $M$, adjacent positions cannot be selected simultaneously.
-
State Design: $f[i][0/1]$ indicates the maximum profit when deciding at position $i$, whether the current position is not selected (0) or selected (1).
-
Two Times DP Branches:
- Branch A: Forcibly not selecting position $1$. Initialize $f[1][0] = 0, f[1][1] = -\text{INF}$. After running linear DP, the final answer may be found in either $f[M][0]$ or $f[M][1]$ (since position $1$ is not selected, position $M$ can be either selected or not).
- Branch B: Forcibly selecting position $1$. Initialize $f[1][0] = -\text{INF}, f[1][1] = A[1]$. After running linear DP, the final answer can only be derived from $f[M][0]$ (since position $1$ is selected, position $M$ must be forcibly unselected).
-
Global Optimal Solution: Take the maximum value from the valid terminal states of the two branches.
C++ Standard Source Code (NOIP Style)
The following code provides a complete implementation of circular stone merging (Doubling Method) and maximum non-adjacent profit (Two Times DP Method) in one program.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 405; // For Doubling, the array size must be doubled 2 * 200 = 400
const int INF = 0x3f3f3f3f;
int a[MAXN];
int s[MAXN];
int f_min[MAXN][MAXN];
// Array for linear DP circular cut model
int v[MAXN];
int dp[MAXN][2];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
if (!(cin >> m)) return 0;
// ==================== Model 1: Circular Stone Merging (Breaking into Chain) ====================
for (int i = 1; i <= m; ++i) {
cin >> a[i];
a[i + m] = a[i]; // Core: Doubling sequence, mapping the circle to double length chain
}
int n = 2 * m;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + a[i]; // Prefix sum boundary extended to 2M
}
// Interval DP Initialization
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
f_min[i][j] = (i == j) ? 0 : INF;
}
}
// Standard interval DP topological sequence recursion
for (int len = 2; len <= m; ++len) { // Fatal pitfall: The upper limit of the merged interval length is still M, not 2M!
for (int l = 1; l <= n - len + 1; ++l) {
int r = l + len - 1;
int score = s[r] - s[l - 1];
for (int k = l; k < r; ++k) {
f_min[l][r] = min(f_min[l][r], f_min[l][k] + f_min[k + 1][r] + score);
}
}
}
// Horizontally scan the minimum value among all linear valid intervals of length M
int ans_merge = INF;
for (int l = 1; l <= m; ++l) {
ans_merge = min(ans_merge, f_min[l][l + m - 1]);
}
// ==================== Model 2: Circular Maximum Non-Adjacent Profit (Two Times DP) ====================
for (int i = 1; i <= m; ++i) {
cin >> v[i];
}
// ---- First DP: Forcibly not selecting position 1 ----
dp[1][0] = 0;
dp[1][1] = -INF; // Block selection of 1
for (int i = 2; i <= m; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + v[i];
}
int res1 = max(dp[m][0], dp[m][1]); // Position 1 not selected, position M can be either selected or not
// ---- Second DP: Forcibly selecting position 1 ----
dp[1][0] = -INF; // Block not selecting 1
dp[1][1] = v[1];
for (int i = 2; i <= m; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + v[i];
}
int res2 = dp[m][0]; // Fatal pitfall: Position 1 selected, position M must be in the unselected state (0)
int ans_select = max(res1, res2);
cout << ans_merge << " " << ans_select << "\n";
return 0;
}NOIP Practical Pitfall Guide
1. Out of Bounds Control for Interval Length $len$ When Breaking the Circle into a Chain
- Phenomenon: When using doubling techniques to handle circular interval DP, competitors mistakenly wrote the outermost interval length enumeration as
for (int len = 2; len <= 2 * m; ++len). This leads to the algorithm trying to compute and merge a length exceeding the original circular capacity "superfluous interval" (for example, merging the 1st pile of stones with the duplicated 1st pile into a nonexistent answer), directly causing semantic errors and numerical overflow. - Preventive Measures: Although the sequence length has been doubled to $2M$, the upper limit of the interval length in state transitions is still $M$. Doubling is only to provide aligned space for all possible circular cut points, not to merge $2M$ elements.
2. Illegal Overlap in Terminal State Updates During Two Times DP Boundary Control
- Phenomenon: In the second DP of "forcibly selecting position 1", the final answer is collected by directly copying
max(dp[m][0], dp[m][1]). This introduces post-effect contamination in circular logic: both position 1 and position $M$ are selected simultaneously, rendering the circular constraint meaningless. - Preventive Measures: Clearly draw the boundary control matrix. If the starting point is forcibly selected, then the terminal state can only be contributed by the state dimension excluding the starting point (e.g.,
dp[m][0]), and do not overlook special cases for terminal states.