Overview

We want to find the minimum total cost to paint the planks such that no two adjacent planks have the same color. By optimizing the dynamic programming transitions using the “minimum value and the second minimum value corresponding to a different color”, this can be solved in \(O(NK)\) time.

Analysis

Using the Last Used Color as the State

Consider painting the planks from left to right. Since the colors available for the next plank depend on the color of the immediately preceding plank, we define the following state:

\(dp[i][j]\): the minimum cost to paint planks \(1\) through \(i\) satisfying the condition, with plank \(i\) painted in color \(j\).

Since the first plank has no adjacency constraints:

\(dp[1][j] = C_{1,j}\)

To paint plank \(i\) with color \(j\), the color of plank \(i-1\) must be different from \(j\), so:

\(dp[i][j] = C_{i,j} + \min_{k \ne j} dp[i-1][k]\)

The answer is the minimum over all possible choices for the color of the last plank:

\(\min_{1 \le j \le K} dp[N][j]\)

However, if we check all colors other than \(j\) for each state, the time complexity becomes \(O(NK^2)\). Even with \(NK \le 10^6\), this will not finish in time when \(K\) is large.

Optimization Using the Minimum and Second Minimum

What we need is “the minimum value excluding a specific color.” Therefore, we maintain the following three values for the previous plank:

• minimum: the minimum cost among all colors
• minimumColor: one of the colors that achieves this minimum cost
• secondMinimum: the minimum cost among colors other than minimumColor

When painting plank \(i\) with color \(j\), the minimum cost up to the previous plank can be chosen as follows:

• If \(j \ne \text{minimumColor}\), use minimum.
• If \(j = \text{minimumColor}\), use secondMinimum because the same color cannot be used.

This allows us to compute each state in \(O(1)\) time.

For example, if the costs up to the previous plank are \([4,4,9]\) for each color, and we choose color \(1\) as achieving the minimum, the second minimum is \(4\) from color \(2\).

Here, the second minimum does not mean “a value strictly greater than the minimum.” It is important that as long as it corresponds to a different color, its value may be equal to the minimum.

Algorithm

For each plank, we compute the three values for the current plank from the three values of the previous plank.

1. Set the initial values as follows:
   • minimum = 0
   • secondMinimum = 0
   • minimumColor = -1

Since colors are handled from \(0\) to \(K-1\) in the code, no color matches minimumColor for the first plank. As a result, only the painting cost itself is computed for all colors.

1. Initialize the information for the current plank:

   • nextMinimum = INF
   • nextSecondMinimum = INF
   • nextMinimumColor = -1

2. Read the cost of each color \(j\), and compute the minimum cost value to paint the current plank with that color:

   • If \(j = \text{minimumColor}\), value = cost + secondMinimum
   • Otherwise, value = cost + minimum

3. Using value, update the minimum and second minimum for the current plank:

   • If value < nextMinimum:
     • Move the current minimum to the second minimum.
     • Update the minimum to value and record its color.
   • Otherwise, if value < nextSecondMinimum:
     • Update the second minimum to value.

4. After processing all colors, carry over the current plank’s information for computing the next plank.

After processing all planks, output minimum.

The value for each color is the DP transition itself, and because the updates correctly maintain the minimum and second minimum needed for the next plank, the overall minimum cost is ultimately obtained.

Complexity

• Time complexity: \(O(NK)\)
• Space complexity: \(O(1)\)

Each color of each plank is processed once. Since the input costs are used for computation on the fly, there is no need to store a cost table or a DP array.

Key Implementation Points

• Use a 64-bit integer for the total cost.
  The total cost can be up to \(N \times 10^9 \le 10^{14}\), so long long is required in C++. In the code, INF = (1LL << 62) is sufficiently larger than this value.

• Values equal to the minimum should also be candidates for the second minimum.
  Even when value == nextMinimum, it must be able to update the second minimum as a different color. In the code, it does not enter the first if branch and is handled in the following else if branch.

• Avoid overwriting the previous plank’s information prematurely.
  While computing all colors for the current plank, the information of the previous plank must be kept fixed. Therefore, variables like nextMinimum are used for updates.

• \(N=1\) can be handled with the same logic.
  Due to the initialization, the value for the first plank becomes the input cost itself, and the minimum among them will be the answer.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    constexpr long long INF = (1LL << 62);
    long long minimum = 0, secondMinimum = 0;
    int minimumColor = -1;

    for (int i = 0; i < N; ++i) {
        long long nextMinimum = INF, nextSecondMinimum = INF;
        int nextMinimumColor = -1;

        for (int j = 0; j < K; ++j) {
            long long cost;
            cin >> cost;

            long long value = cost +
                (j == minimumColor ? secondMinimum : minimum);

            if (value < nextMinimum) {
                nextSecondMinimum = nextMinimum;
                nextMinimum = value;
                nextMinimumColor = j;
            } else if (value < nextSecondMinimum) {
                nextSecondMinimum = value;
            }
        }

        minimum = nextMinimum;
        secondMinimum = nextSecondMinimum;
        minimumColor = nextMinimumColor;
    }

    cout << minimum << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.