Exploring Circular Dynamic Programming Techniques: Breaking Chains and Boundary Fixing

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.

Classic NOIP/Luogu Problems

1. Luogu P1880 [NOI1995] Stone Merging

Problem Description: $N$ piles of stones are placed around a circular playground. The goal is to merge the stones into one pile in order. It is stipulated that only adjacent piles can be merged into a new pile, and the number of stones in the new pile is recorded as the score for that merge. Find the minimum and maximum scores after merging.
Essence and Problem-Solving Ideas: The foundational problem of circular interval dynamic programming.
Core Idea: This is a typical application model of "breaking the circle into a chain". By using $A[i+N] = A[i]$, the circular ring is flattened into a linear segment of length $2N$. Under the constraint of the outer loop $len \text{ ≤ } N$, calculate all f_min[l][r] and f_max[l][r] in the two-dimensional space. Finally, traverse all valid circular breakpoints (i.e., $l \text{ in } [1, N]$) to collect the global min and max extremes within the interval $[l, l+N-1]$.

2. Luogu P6064 [USACO05JAN] Naptime G

Problem Description: There are $N$ hours in a day, and each hour has a specific vitality recovery value $U_i$. The cow needs to sleep for $B$ hours each day, and these $B$ hours can be divided into several segments. There is a key restriction: the first hour of each sleep segment cannot recover any vitality due to the preparation phase. Additionally, the $N$th hour of each day is adjacent to the 1st hour of the next day (circular time axis). Find the maximum total vitality that can be recovered each day.
Essence and Problem-Solving Ideas: A circular state machine DP with pre-loss states.
State Design: Let $f[i][j][0/1]$ indicate the decision at the $i$th hour, with $j$ hours already slept, and whether the current hour is in the "not sleeping (0)" or "sleeping (1)" state.
Core Idea: The time axis is circular, meaning if the $N$th hour is sleeping, the 1st hour can directly enjoy vitality recovery (without preparation phase). Using the "boundary conversion to multiple DP" strategy:
1. First DP: Assume the 1st hour is not sleeping or in preparation phase, initialize $f[1][1][1] = 0, f[1][0][0] = 0$, and others as -INF. Linearly propagate to $N$, and the final answer is taken as $\text{max}(f[N][B][0], f[N][B][1])$.
2. Second DP: Forcibly ensure the $N$th hour and the 1st hour are in continuous sleep. That is, the 1st hour directly enters state 1 and can harvest benefits. Initialize $f[1][1][1] = U_1$, and others as -INF. Linearly propagate to $N$, ensuring that the $N$th hour is indeed connected to the 1st hour, and the final answer can only be taken as f[N][B][1]. The two rounds of DP cover all marginal possibilities of states on the circle, thoroughly eliminating post-effect contamination.