Overview

This problem asks us to select some checkpoints and visit them in ascending order of their indices such that the number of visited checkpoints is at least \(K\), the number of visits to each terrain type is even, and the total travel cost is minimized.

We can solve this problem using dynamic programming, where we represent the parity of the visit count for each terrain type as a bitmask. The DP state will track the last visited checkpoint, the number of visited checkpoints, and the parity state.

Analysis

Once we choose the set of checkpoints to visit, the visiting order is uniquely determined in ascending order of their indices.

For example, if the visited checkpoints are \(p_1 < p_2 < \cdots < p_s\), the path must be:

\[ 0 \to p_1 \to p_2 \to \cdots \to p_s \to N+1 \]

Therefore, the problem can be framed as deciding which checkpoints to choose.

However, exhaustively searching whether to visit or not for each checkpoint would take \(2^N\) steps, which is impossible since \(N \leq 150\).

Thus, we utilize the following properties.

We only need to track the parity of the terrain types

For each terrain type, only whether the number of visits is even or odd matters.

Since there are \(M \leq 8\) terrain types, we can represent the parity state as an \(M\)-bit bitmask.

For example, when \(M=3\), we can map each bit of the mask as follows:

• bit \(0\): whether the number of visits to type \(1\) is odd
• bit \(1\): whether the number of visits to type \(2\) is odd
• bit \(2\): whether the number of visits to type \(3\) is odd

If a checkpoint has terrain type \(t\), visiting this checkpoint flips bit \(t-1\).

For the visit counts of all types to be even at the end, the final mask must be \(0\).

Only whether the number of visits is at least \(K\) matters

Regarding the number of visits, we need to track the exact count as long as it is less than \(K\).

On the other hand, if we have already visited \(K\) or more checkpoints, we do not need the exact count beyond that.

Thus, we track the number of visits as:

\[ \min(\text{actual number of visits}, K) \]

In other words, in our DP state, the count \(K\) represents “visited at least \(K\) checkpoints”.

Algorithm

We define the DP state as follows:

\[ dp[c][i][mask] \]

defined as the minimum cost to travel from location \(0\) to location \(i\), where:

• The current (last visited) location is \(i\)
• The number of visited checkpoints is \(c\)
  • where \(c=K\) represents “visited at least \(K\) checkpoints”
• The parity state of the terrain types is \(mask\)

Here, \(i\) ranges from \(0\) to \(N\). Location \(0\) represents the starting point.

The initial state is:

\[ dp[0][0][0] = 0 \]

Since we have not visited any checkpoints yet, and all parities are even, the mask is \(0\).

Transitions

From state \(dp[c][i][mask]\), let the next visited checkpoint be \(j\).

Since we can only move in the direction of increasing indices, we must have:

\[ i < j \leq N \]

Letting the bit corresponding to the terrain type of checkpoint \(j\) be type_bit[j], the next state will be:

\[ nc = \min(K, c+1) \]

\[ nmask = mask \oplus type\_bit[j] \]

Thus, the transition is:

\[ dp[nc][j][nmask] = \min( dp[nc][j][nmask], dp[c][i][mask] + C_{i,j} ) \]

where \(\oplus\) represents the bitwise XOR operation.

Answer

Finally, we move directly from some checkpoint \(i\) to the observatory \(N+1\).

To satisfy the conditions, we need:

• At least \(K\) checkpoints visited
• The parity state is \(0\)

Therefore, the answer is:

\[ \min_{0 \leq i \leq N} \left( dp[K][i][0] + C_{i,N+1} \right) \]

If this value is not updated (remains infinity), no valid path exists, so we output \(-1\).

Complexity

Let \(S = 2^M\).

• Time Complexity: \(O(KN^2 2^M)\)
  • Since \(K \leq N\), the worst-case time complexity is \(O(N^3 2^M)\).
• Space Complexity: \(O(KN2^M + N^2)\)
  • \(O(KN2^M)\) for the DP table
  • \(O(N^2)\) for the cost table

Implementation Points

• The maximum cost is up to \(10^9\), and the path length can be up to around \(N+1\), so the answer may exceed the range of a 32-bit integer. Use long long (or a 64-bit integer).

• INF should be set to a sufficiently large value, such as 1LL << 62.

• Since the terrain type \(t_i\) is 1-indexed, the corresponding bit is 1 << (t_i - 1).

• In the layer where the visit count is \(c=K\), visiting more checkpoints will transition to the same layer. Since the location index still increases, the DP will be updated correctly as long as we process \(i\) in ascending order.

• In the implementation, we can speed up the execution by skipping transitions from states where the number of remaining checkpoints is insufficient to reach \(K\) visits. This optimization does not affect the final answer.

  Source Code

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

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

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

    vector<int> type_bit(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        int t;
        cin >> t;
        type_bit[i] = 1 << (t - 1);
    }

    int Q = N + 2;
    vector<long long> C(1LL * Q * Q, 0);
    for (int a = 0; a <= N; a++) {
        for (int b = a + 1; b <= N + 1; b++) {
            cin >> C[1LL * a * Q + b];
        }
    }

    const long long INF = (1LL << 62);
    int S = 1 << M;
    int P = N + 1;

    vector<long long> dp(1LL * (K + 1) * P * S, INF);
    vector<long long> layer_off(K + 1), node_off(P);

    for (int c = 0; c <= K; c++) layer_off[c] = 1LL * c * P * S;
    for (int i = 0; i <= N; i++) node_off[i] = 1LL * i * S;

    dp[layer_off[0] + node_off[0]] = 0;

    for (int c = 0; c <= K; c++) {
        bool capped = (c == K);
        int nc = capped ? K : c + 1;

        int i_start, i_end, max_j;

        if (capped) {
            i_start = (K == 0 ? 0 : K);
            i_end = N - 1;
            max_j = N;
        } else {
            if (c == 0) {
                i_start = i_end = 0;
            } else {
                i_start = c;
                i_end = N - (K - c);
            }
            max_j = N - (K - (c + 1));
        }

        if (i_end < i_start) continue;

        long long dst_layer = layer_off[nc];

        for (int i = i_start; i <= i_end; i++) {
            long long* src = dp.data() + layer_off[c] + node_off[i];
            const long long* crow = C.data() + 1LL * i * Q;

            for (int mask = 0; mask < S; mask++) {
                long long val = src[mask];
                if (val == INF) continue;

                for (int j = i + 1; j <= max_j; j++) {
                    int nmask = mask ^ type_bit[j];
                    long long nv = val + crow[j];
                    long long &ref = dp[dst_layer + node_off[j] + nmask];
                    if (nv < ref) ref = nv;
                }
            }
        }
    }

    long long ans = INF;
    long long final_layer = layer_off[K];

    for (int i = 0; i <= N; i++) {
        long long val = dp[final_layer + node_off[i]];
        if (val == INF) continue;

        long long nv = val + C[1LL * i * Q + (N + 1)];
        if (nv < ans) ans = nv;
    }

    if (ans == INF) cout << -1 << '\n';
    else cout << ans << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.