Luogu P1133 Review: From Linear DP to Cutting the Circle into a Line

Introduction

I recently solved a classic circular DP problem. It was quite deceptive: I designed a seemingly correct linear DP model that actually ignored the problem’s central circular constraint. This article retraces the entire process, from a 70-point linear solution, through a 90-point incorrect patch, to the final 100-point accepted solution that cuts the circle into a line. Along the way, I will examine the mistakes in my reasoning and the key to modeling the problem correctly.

Problem Analysis

P1133 The Leader’s Garden

The essential parts of the problem are:

1. Layout: A circular arrangement.
2. Constraint: Every tree must be taller than both neighbors or shorter than both neighbors, forming a peak or a valley.
3. Objective: Maximize the total ornamental value.

This is a dynamic programming problem, and state design is the key. To store the input ornamental values, I used a Plant_Position structure, where pos[i].ten, pos[i].twenty, and pos[i].thirty hold the corresponding values at position i.

To determine whether a planting at position i is valid, we need both the height at i-1 and the direction of the change from i-2 to i-1. Only then can we determine which direction is allowed at i. This calls for a three-dimensional state: dp[i][j][k].

• i: We are considering the ith tree.
• j: The height of the ith tree. I use 1, 2, 3 to represent heights 10, 20, 30.
• k: The shape of the sequence at the ith tree.
  • k=0: The ith tree is a valley: H[i-1] > H[i], so the change from i-1 to i is downward.
  • k=1: The ith tree is a peak: H[i-1] < H[i], so the change from i-1 to i is upward.

The value of dp[i][j][k] is the maximum ornamental value under these definitions.

Algorithm Design and Implementation

V1.0: A First Attempt with Linear DP (70 Points)

Design

My initial approach completely ignored the circular constraint and treated the garden as a linear sequence from 1 to n. The state dp[i][j][k] above gives us all the valid transition equations.

State transitions in detail:

1. Target state: dp[i][1][0] (height 10, valley/downward)

   • Reasoning: To descend to height 10, the previous position i-1 must have height 20 or 30. To form a valley, i-1 must also be a peak—an upward state with k=1.
   • Equation: dp[i][1][0] = max(dp[i-1][2][1], dp[i-1][3][1]) + pos[i].ten

2. Target state: dp[i][2][0] (height 20, valley/downward)

   • Reasoning: To descend to height 20, the previous position i-1 must have height 30. It must be a peak—an upward state with k=1.
   • Equation: dp[i][2][0] = dp[i-1][3][1] + pos[i].twenty

3. Target state: dp[i][2][1] (height 20, peak/upward)

   • Reasoning: To ascend to height 20, the previous position i-1 must have height 10. It must be a valley—a downward state with k=0.
   • Equation: dp[i][2][1] = dp[i-1][1][0] + pos[i].twenty

4. Target state: dp[i][3][1] (height 30, peak/upward)

   • Reasoning: To ascend to height 30, the previous position i-1 may have height 10 or 20. It must be a valley—a downward state with k=0.
   • Equation: dp[i][3][1] = max(dp[i-1][1][0], dp[i-1][2][0]) + pos[i].thirty

Unreachable states:

• dp[i][1][1] (ascending to the lowest height) and dp[i][3][0] (descending to the highest height) are impossible. Their values should remain at a very small sentinel value and stay out of the calculation.

Figure legend: The state definition labels i as the position, j as the height, and k as the height relationship to the previous tree. k=0 is downward (H[i-1] > H[i]); k=1 is upward (H[i-1] < H[i]). The red and green calculations work through the four transitions on the sample.

Implementation

This implementation simply loops from i=1 to n, then takes the maximum over all valid states in dp[n] as the result.

70-point submission record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 1e5 + 5;

struct Plant_Position {
    ll ten, twenty, thirty;
};

ll n, dp[maxn][8][7];
Plant_Position pos[maxn];

void dp_10_0(int idx) {
    dp[idx][1][0] = max(dp[idx - 1][2][1], dp[idx - 1][3][1]) + pos[idx].ten;
}

void dp_20_0(int idx) {
    dp[idx][2][0] = dp[idx - 1][3][1] + pos[idx].twenty;
}

void dp_20_1(int idx) {
    dp[idx][2][1] = dp[idx - 1][1][0] + pos[idx].twenty;
}

void dp_30_1(int idx) {
    dp[idx][3][1] = max(dp[idx - 1][1][0], dp[idx - 1][2][0]) + pos[idx].thirty;
}

ll DP() {
    for (int i = 1; i <= n; i++) {
        dp_10_0(i);
        dp_20_0(i);
        dp_20_1(i);
        dp_30_1(i);
    }
    return max(max(dp[n][1][0], dp[n][3][1]), max(dp[n][2][0], dp[n][2][1]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i].ten >> pos[i].twenty >> pos[i].thirty;
    }
    cout << DP();
    return 0;
}

What Went Wrong

• Root cause:
  This computes the optimum for a linear arrangement, but the problem requires a circular arrangement. The states at positions n and 1 in the linear optimum may fail the alternating-height constraint, making the solution invalid for the circular problem.

V2.0: An Incorrect “Patch” (90 Points)

Design

After submitting V1.0, I realized that I had missed the circular constraint. I then came up with a flawed correction: compute the linear optimum first, then check whether it satisfies the circular constraint.

My first implementation of this idea was a complicated, cumbersome while loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

ans.push_back(dp[n][1][0]);
ans.push_back(dp[n][2][0]);
ans.push_back(dp[n][2][1]);
ans.push_back(dp[n][3][1]);
sort(ans.begin(), ans.end());
bool y[5] = {0};
while (1) {
    if (ans.back() == dp[n][2][0] && !y[0]) {
        if (pos[1].twenty < pos[1].thirty) {
            cout << ans.back();
            return;
        }
        else {
            y[0] = true;
            ans.pop_back();
            continue;
        }
    }
    if (ans.back() == dp[n][2][1] && !y[1]) {
        if (pos[1].twenty < pos[1].ten) {
            cout << ans.back();
            return;
        }
        else {
            y[1] = true;
            ans.pop_back();
            continue;
        }
    }
    cout << ans.back();
    return;
}

I eventually reduced this complicated while loop to two if statements:

1
2
3
4
5
6
7

if (pos[1].twenty > pos[1].ten) {
    dp[n][2][1] = 0;
}
if (pos[1].twenty > pos[1].thirty) {
    dp[n][2][0] = 0;
}
cout << max(max(dp[n][1][0], dp[n][3][1]), max(dp[n][2][0], dp[n][2][1]));

Although the if version is much shorter, the underlying faulty reasoning is the same. The “patch” tries to take the few optimal candidates produced by linear DP and use a set of checks to infer and verify whether their starting points are valid.

The checks work as follows:

1. Unrestricted cases: If the linear optimum ends at dp[n][1][0] (H=10, downward) or dp[n][3][1] (H=30, upward), accept it directly.

   • Inference: If H[n]=10, closing the circle requires H[1] > 10, so H[1] may be 20 or 30. Because there are two choices, the code assumes that a valid starting point can always be found and no intervention is needed. The same reasoning applies to H[n]=30.

2. Restricted case 1: Consider a path ending at dp[n][2][1] (H=20, upward).

   • Inference: This ending state implies H[n-1]=10. To close the circle, H[1] must be less than H[n]=20, so H[1] must be 10.
   • Verification: The code makes a greedy check: if (pos[1].twenty > pos[1].ten). Its reasoning is: “If planting 20 at the starting point gives a higher ornamental value than planting 10, a genuinely optimal path could not have chosen 10 at the beginning.” Under this greedy assumption, when the condition holds, the path requiring a starting height of 10 cannot be optimal, so dp[n][2][1] = 0 invalidates it.

3. Restricted case 2: Consider a path ending at dp[n][2][0] (H=20, downward).

   • Inference: This ending state implies H[n-1]=30. To close the circle, H[1] must be greater than H[n]=20, so H[1] must be 30.
   • Verification: Similarly, the code makes the greedy check if (pos[1].twenty > pos[1].thirty). If planting 20 gives a higher value, it assumes that the path requiring a starting height of 30 cannot be optimal and invalidates it.

Figure legend: The arrows follow the circular order. The circled candidates and the two conditions at the upper right illustrate the attempted endpoint checks: discard dp[n][2][1] or dp[n][2][0] based on the ornamental values at the first position.

Implementation

90-point submission record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 1e5 + 5;

struct Plant_Position {
    ll ten, twenty, thirty;
};

ll n, dp[maxn][8][7];
Plant_Position pos[maxn];
vector<ll> ans;

void dp_10_0(int idx) {
    dp[idx][1][0] = max(dp[idx - 1][2][1], dp[idx - 1][3][1]) + pos[idx].ten;
}

void dp_20_0(int idx) {
    dp[idx][2][0] = dp[idx - 1][3][1] + pos[idx].twenty;
}

void dp_20_1(int idx) {
    dp[idx][2][1] = dp[idx - 1][1][0] + pos[idx].twenty;
}

void dp_30_1(int idx) {
    dp[idx][3][1] = max(dp[idx - 1][1][0], dp[idx - 1][2][0]) + pos[idx].thirty;
}

void DP() {
    for (int i = 1; i <= n; i++) {
        dp_10_0(i);
        dp_20_0(i);
        dp_20_1(i);
        dp_30_1(i);
    }
    if (pos[1].twenty > pos[1].ten) {
        dp[n][2][1] = 0;
    }
    if (pos[1].twenty > pos[1].thirty) {
        dp[n][2][0] = 0;
    }
    cout << max(max(dp[n][1][0], dp[n][3][1]), max(dp[n][2][0], dp[n][2][1]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i].ten >> pos[i].twenty >> pos[i].thirty;
    }
    DP();
    return 0;
}

What Went Wrong

• Fundamental flaw:
  This approach does not fail because the if-statement patch is insufficiently clever. Quite the opposite: it neatly condenses the intention of the earlier while loop and is a very good patch in terms of expressing that logic.

  The real error lies in the fundamental algorithm design. This kind of after-the-fact repair is like beautifully paving a road that goes in the wrong direction: however good the road is, it cannot take you to the right destination.

  The central fallacy is the assumption that the circular optimum must be among the linear optima. In reality, the linear portion of the true circular optimum may not be optimal at all. The code checks only a handful of linear-optimal candidates. The actual answer may already have been discarded during the first DP because its score was not high enough on the line, leaving it no chance of reaching the final if checks. This is a classic local-optimum trap.

V3.0: The Correct Solution—Cut the Circle into a Line (AC)

Design

The correct approach is to abandon after-the-fact repair and use the standard pattern for circular problems: cut the circle into a line.

The central idea is to split a difficult circular problem into a few independent linear problems with explicit starting and ending constraints.

Specifically, an outer loop fixes the height of the first tree (第 1 棵树) in turn to each of the three possibilities: H=10, H=20, and H=30. For each case, run an independent linear DP from 2 to n. At the end, use the fixed starting point to filter the states in dp[n] for validity.

Figure legend: The three diagrams fix the first tree to each possible height. The notes marked “take max” identify the eligible ending states for that starting height; the red formulas are the same linear transitions used in each independent run.

Feasibility Analysis

• Time complexity: Each DP run takes O(n). There are 3 independent runs, so the overall time complexity remains O(n).
• Space complexity: O(n).
• Conclusion: The approach is efficient and feasible.

Implementation

Accepted submission record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 1e5 + 5;

struct Plant_Position {
    ll ten, twenty, thirty;
};

ll n, dp[maxn][5][5], ans;
Plant_Position pos[maxn];

void DP() {
    ll ans = 0;
    for (int i = 1; i <= 3; i++) {
        if (i == 1) {
            dp[1][1][0] = pos[1].ten;
        }
        else if (i == 2) {
            dp[1][2][0] = pos[1].twenty, dp[1][2][1] = pos[1].twenty;
        }
        else if (i == 3) {
            dp[1][3][1] = pos[1].thirty;
        }
        for (int i = 2; i <= n; i++) {
            dp[i][1][0] = max(dp[i - 1][2][1], dp[i - 1][3][1]) + pos[i].ten;
            dp[i][2][0] = dp[i - 1][3][1] + pos[i].twenty;
            dp[i][2][1] = dp[i - 1][1][0] + pos[i].twenty;
            dp[i][3][1] = max(dp[i - 1][1][0], dp[i - 1][2][0]) + pos[i].thirty;
        }
        if (i == 1) {
            ans = max(ans, max(dp[n][2][1], dp[n][3][1]));
        }
        else if (i == 2) {
            ans = max(ans, max(dp[n][1][0], dp[n][3][1]));
        }
        else if (i == 3) {
            ans = max(ans, max(dp[n][1][0], dp[n][2][0]));
        }
        memset(dp, 0, sizeof(dp));
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i].ten >> pos[i].twenty >> pos[i].thirty;
    }
    DP();
    return 0;
}

• Implementation details
  The essence of this approach is to turn the circular constraint from a difficult final check into case analysis built into the design. Once the starting point is fixed, the final filtering of ending states works as follows:

  1. Starting height H[1]=10 (valley):

     • To close the circle, H[n] must be a peak with H[n] > H[1].
     • Valid ending states: dp[n][2][1] (H=20, upward) and dp[n][3][1] (H=30, upward).
     • Candidate answer: max(dp[n][2][1], dp[n][3][1])

  2. Starting height H[1]=20 (peak or valley):

     • To close the circle, if H[n] is a peak, it must satisfy H[n] > H[1]; if it is a valley, it must satisfy H[n] < H[1].
     • Valid ending states: dp[n][3][1] (H=30, upward) and dp[n][1][0] (H=10, downward).
     • Candidate answer: max(dp[n][3][1], dp[n][1][0])

  3. Starting height H[1]=30 (peak):

     • To close the circle, H[n] must be a valley with H[n] < H[1].
     • Valid ending states: dp[n][1][0] (H=10, downward) and dp[n][2][0] (H=20, downward).
     • Candidate answer: max(dp[n][1][0], dp[n][2][0])

  The final answer is the largest of these three candidates. This precise filtering ensures that the final solution is valid.

Takeaways

1. Modeling is the key: Recognizing and handling the central circular structure is the key to this problem. Applying a linear model directly takes the solution fundamentally away from what the problem asks.
2. Be wary of patches: When an algorithm has a flaw, complicated after-the-fact checks are often wrong or incomplete. The right response is to return to the design and consider how to incorporate the constraint into the model from the beginning.
3. Master the standard pattern: Cutting a circle into a line is a general and powerful idea for almost all circular DP and circular-array problems. It is a technique worth knowing well.