Overview

This problem asks for the minimum cost to paint \(N\) boards using \(K\) colors such that no two adjacent boards have the same color. We can solve this efficiently within the constraints by optimizing dynamic programming (DP).

Analysis

Naive Approach

First, consider the following dynamic programming (DP) state: - \(dp[i][j] =\) “the minimum total cost to paint boards \(1\) through \(i\), such that board \(i\) is painted with color \(j\)”

When painting board \(i\) with color \(j\), the preceding board \(i - 1\) can be painted with any color \(k\) other than \(j\) (\(k \neq j\)). Therefore, the transition formula is as follows:

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

Directly computing this transition would require: - Number of boards: \(N\) - Colors for the current board: \(K\) choices - Colors for the preceding board: scan \(K - 1\) choices to find the minimum value

In this case, the overall time complexity is \(O(N \times K^2)\). Under the problem constraints, \(N \times K \leq 10^6\). However, since \(K\) can be up to \(10^6\), \(N \times K^2\) can reach up to \(10^{12}\), which will exceed the time limit and result in a TLE (Time Limit Exceeded).

Optimization

Looking at the term \(\min_{k \neq j} dp[i - 1][k]\), we can see that searching for the minimum among \(K\) elements from scratch every time is redundant.

In fact, by precalculating just the minimum value and the second minimum value from the DP values of the preceding board \(i - 1\), we can compute the transition for each color \(j\) in \(O(1)\) time.

• Let \(idx_1\) be the color that achieves the minimum value for the preceding board, and \(min_1\) be this minimum value.
• Let \(min_2\) be the second minimum value for the preceding board.

Then, the minimum transition cost when painting board \(i\) with color \(j\) is as follows: - If \(j \neq idx_1\): We can choose color \(idx_1\), which had the lowest cost for the preceding board, so the transition cost is \(min_1\). - If \(j = idx_1\): We cannot choose \(idx_1\) because adjacent boards would share the same color. Thus, we have no choice but to pick the color with the next lowest cost, so the transition cost is \(min_2\).

By using the minimum and the second minimum values in this way, each color \(j\) can be updated in \(O(1)\) time, allowing each board to be processed in \(O(K)\) time.

Algorithm

1. Initialization:
   • Initialize the array with \(dp[j] = C_{1, j}\) (the cost to paint board \(1\) with color \(j\)).
2. Updates from Board \(2\) to \(N\):
   • Scan the previous \(dp\) array to find:
     • The minimum value \(min_1\) and its color index \(idx_1\)
     • The second minimum value \(min_2\)
   • For each color \(j\) (\(0 \leq j < K\)), compute the new cost \(next\_dp[j]\) for board \(i\):
     • If \(j == idx_1\), then \(next\_dp[j] = C_{i, j} + min_2\)
     • If \(j \neq idx_1\), then \(next\_dp[j] = C_{i, j} + min_1\)
   • Overwrite the \(dp\) array with \(next\_dp\).
3. Computing the Answer:
   • The minimum value in the \(dp\) array after painting up to board \(N\) is the answer.

Complexity

• Time Complexity: \(O(N \times K)\)
  • For each board, finding the minimum and second minimum values takes \(O(K)\), and updating each color takes \(O(K)\). Since there are \(N\) boards in total, the overall time complexity is \(O(N \times K)\).
  • Given the constraint \(N \times K \leq 10^6\), this runs well within the time limit.
• Space Complexity: \(O(K)\)
  • Since we only need to keep the DP table from the preceding board, the computation can be done using only two arrays of size \(K\). Since \(K \le 10^6\), memory limit is not an issue.

Implementation Notes

• Preventing Overflow:

  • Since \(C_{i, j} \leq 10^9\) and \(N \leq 10^5\), the total cost can reach around \(10^{14}\). This far exceeds the maximum limit of a 32-bit signed integer (approximately \(2 \times 10^9\)), so use a 64-bit integer type (long long in C++) for the DP table and variables that handle costs.

• Finding the Minimum and Second Minimum:

  • In a single pass, if the current value is smaller than \(min_1\), update \(min_2\) to \(min_1\) before updating \(min_1\). If the current value is greater than or equal to \(min_1\) but smaller than \(min_2\), update only \(min_2\). This allows both values to be retrieved correctly in a single scan (\(O(K)\)).

    Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> dp(K);
    for (int j = 0; j < K; ++j) {
        cin >> dp[j];
    }

    for (int i = 1; i < N; ++i) {
        long long min1 = -1, min2 = -1;
        int idx1 = -1;

        for (int j = 0; j < K; ++j) {
            long long val = dp[j];
            if (idx1 == -1 || val < min1) {
                min2 = min1;
                min1 = val;
                idx1 = j;
            } else if (min2 == -1 || val < min2) {
                min2 = val;
            }
        }

        vector<long long> next_dp(K);
        for (int j = 0; j < K; ++j) {
            long long c;
            cin >> c;
            if (j == idx1) {
                next_dp[j] = c + min2;
            } else {
                next_dp[j] = c + min1;
            }
        }
        dp = move(next_dp);
    }

    long long ans = dp[0];
    for (int j = 1; j < K; ++j) {
        ans = min(ans, dp[j]);
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.