Overview

In this problem, we want to paint \(N\) planks using \(K\) colors to minimize the total cost such that adjacent planks have different colors. This is a typical sequence DP, but a naive transition is too slow, so we speed it up using the minimum and second minimum values.

Analysis

DP Definition

Consider determining the colors from left to right. Since only the color of plank \(i\) affects the choice for plank \(i+1\), the following DP is natural:

\[\mathrm{dp}[i][j] = (\text{minimum cost to paint planks } 1 \sim i \text{ such that plank } i \text{ is painted with color } j)\]

The initial values are \(\mathrm{dp}[1][j] = C_{1,j}\), and the transition is:

\[\mathrm{dp}[i][j] = C_{i,j} + \min_{j' \neq j} \mathrm{dp}[i-1][j']\]

The answer is \(\min_j \mathrm{dp}[N][j]\).

Naive Implementation is Too Slow

If we implement the transition above directly according to its definition, taking the minimum over all \(j' \neq j\) for each \((i, j)\) takes \(O(NK^2)\) time. Under only the constraint \(N \times K \le 10^6\), \(K\) can be up to \(10^6\) (for instance, even if \(N=1, K=10^6\), or if \(N=1000, K=1000\) where \(NK^2 = 10^9\)), so this will result in TLE.

Key to Optimization

Here we make an important observation. For \(\min_{j' \neq j} \mathrm{dp}[i-1][j']\), let:

• \(j_1\) be the color that gives the minimum value of \(\mathrm{dp}[i-1]\), and \(b_1\) be its value.
• \(b_2\) be the second smallest value of \(\mathrm{dp}[i-1]\) (ties are allowed; simply “the minimum value excluding \(j_1\)”).

Then we can write:

\[\min_{j' \neq j} \mathrm{dp}[i-1][j'] = \begin{cases} b_2 & (j = j_1) \\ b_1 & (j \neq j_1) \end{cases}\]

In other words, “we only use the second minimum when the excluded color matches the color of the minimum.”

Therefore, by keeping track of the three values \(b_1, b_2, j_1\) for each row, the transition can be computed in \(O(1)\) for each \(j\).

Concrete Example

Let \(N=3, K=3\) with the following matrix:

1 5 9
7 2 8
6 4 3

• \(\mathrm{dp}[1] = (1, 5, 9)\). \(b_1 = 1\) (\(j_1 = 1\)), \(b_2 = 5\).
• \(\mathrm{dp}[2][1] = 5 + 7 = 12\) (since color 1 is \(j_1\), we use \(b_2=5\)), \(\mathrm{dp}[2][2] = 1 + 2 = 3\), \(\mathrm{dp}[2][3] = 1 + 8 = 9\). Thus, \(\mathrm{dp}[2] = (12, 3, 9)\), \(b_1 = 3\) (\(j_1 = 2\)), \(b_2 = 9\).
• \(\mathrm{dp}[3][1] = 3 + 6 = 9\), \(\mathrm{dp}[3][2] = 9 + 4 = 13\), \(\mathrm{dop}[3][3] = 3 + 3 = 6\). The minimum is \(6\).

Algorithm

1. While reading the first row, construct \(\mathrm{dp}[j] = C_{1,j}\), and simultaneously find the minimum value \(b_1\), its index \(j_1\), and the second minimum \(b_2\).
2. For \(i = 2, \dots, N\), while reading \(C_{i,j}\):
   • \(\mathrm{ndp}[j] = C_{i,j} + (b_2 \text{ if } j = j_1 \text{ else } b_1)\)
   • Simultaneously update the minimum value of \(\mathrm{ndp}\), its index, and the second minimum.
3. Output the finally obtained \(b_1\) (\(= \min_j \mathrm{dp}[N][j]\)).

To find the minimum and the second minimum in a single pass, you can do the following during the iteration:

if (v < b1) { b2 = b1; b1 = v; j1 = j; }
else if (v < b2) { b2 = v; }

(Be careful not to get the order of updates wrong).

Note that when \(N=1\), the minimum of the first row is directly the answer, which is naturally handled by the flow above. Since \(K \ge 2\) is guaranteed, a solution always exists (if \(K=1\) and \(N\ge2\), it would be impossible, but this is excluded by the constraints).

Complexity

• Time Complexity: \(O(NK)\) (the same order as reading the input, \(NK \le 10^6\))
• Space Complexity: \(O(K)\) (only two DP arrays; no need to store all \(C_{i,j}\))

Implementation Notes

• Perform DP while reading the input: Storing all of \(C\) as an \(N \times K\) 2D array is not impossible since it has at most \(10^6\) elements, but discarding rows after processing reduces the memory to \(O(K)\) and improves cache efficiency.

• Fast I/O: Since the input contains up to \(10^6\) integers (each up to 10 digits), using default cin (without untying/desynchronizing) might be too slow. In C++, custom fast I/O via fread or ios::sync_with_stdio(false) is recommended. In Python, batch reading using sys.stdin.buffer.read() is essential.

• Overflow: The cost can be up to \(10^9\) and there are up to \(10^5\) planks, so the total sum can reach around \(10^{14}\). Since this will overflow a 32-bit int, use a 64-bit integer (long long).

• Swapping DP arrays: Avoid copying by using swap(dp, ndp) (swapping std::vector is \(O(1)\) as it only exchanges internal pointers). In fact, since this solution only requires \(b_1, b_2, j_1\) to compute the next row, we can obtain the answer without even maintaining the dp array itself (the dp array in the code is practically unnecessary and only serves to store values).

• Handling the second minimum: Since \(K \ge 2\), \(b_2\) is guaranteed to exist. Still, for safety, initialize it to a sufficiently large value (\(\infty\)) and guard against overflow when adding to \(\infty\).

  Source Code

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

static char buf[1 << 25];
int bufLen = 0, bufPos = 0;

static inline int gc() {
    if (bufPos == bufLen) {
        bufLen = (int)fread(buf, 1, sizeof(buf), stdin);
        bufPos = 0;
        if (bufLen <= 0) return -1;
    }
    return buf[bufPos++];
}

static inline long long readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9') && c != '-') c = gc();
    bool neg = false;
    if (c == '-') { neg = true; c = gc(); }
    long long x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = gc();
    }
    return neg ? -x : x;
}

int main() {
    int N = (int)readInt();
    int K = (int)readInt();

    const long long INF = (long long)4e18;

    vector<long long> dp(K), ndp(K);

    // first row
    long long best1 = INF, best2 = INF;
    int idx1 = -1;
    for (int j = 0; j < K; j++) {
        long long c = readInt();
        dp[j] = c;
        if (c < best1) { best2 = best1; best1 = c; idx1 = j; }
        else if (c < best2) { best2 = c; }
    }

    for (int i = 1; i < N; i++) {
        long long nb1 = INF, nb2 = INF;
        int nidx1 = -1;
        for (int j = 0; j < K; j++) {
            long long c = readInt();
            long long prev = (j == idx1) ? best2 : best1;
            long long v = (prev >= INF) ? INF : prev + c;
            ndp[j] = v;
            if (v < nb1) { nb2 = nb1; nb1 = v; nidx1 = j; }
            else if (v < nb2) { nb2 = v; }
        }
        swap(dp, ndp);
        best1 = nb1; best2 = nb2; idx1 = nidx1;
    }

    printf("%lld\n", best1);
    return 0;
}

---

This editorial was generated by claude5opus-high.