Solution

Let's define $\texttt{lowestOps}[a][b]$ as the minimum number of operations to see if each horse is in the stables or not, given that we only consider horses in the interval $(\texttt{stableHorses[a]}, \texttt{stableHorses[b]})$, with $\texttt{stableHorses}$ being a sorted list of all the horses that are in the stables.

Why use an open interval? It's to account for the horses with ID's that aren't contained in the range of the ID's of the horses of the stable. For example, if we had a horse with ID $4$, and the horses in the stables were $[6, 7, 10]$, then there would be no way for $\texttt{lowestOps}$ to account for that horse.

To solve this, we can add two more hypothetical horses that are just out of bounds of all the other horses: one at the front and one at the end. This along with the open interval ensures that we can account for all horses excluding the hypothetical ones we've added.

Then, to calculate the value for an interval, we go through all possible roots we can use for the tree of that interval. If we're calculating $\texttt{lowestOps}[a][b]$ with $b-a\geq3$ and we're using a root $c$ ($a<c<b$), then we have the following recurrence relation:

$\texttt{lowestOps}[a][b]=\texttt{lowestOps}[a][c]+\texttt{lowestOps}[c][b]+(\texttt{stableHorses}[b]-\texttt{stableHorses}[a]-1)$

Implementation

Time Complexity: $\mathcal{O}(N^3)$

Copy
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Copy
import java.io.*;
import java.util.Arrays;

public final class genghis {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int horseNum = Integer.parseInt(read.readLine());
		int stableNum = Integer.parseInt(read.readLine());
		int[] stableHorses = new int[stableNum + 2];
		for (int i = 1; i <= stableNum; i++) {

Copy
horse_num = int(input())
stable_num = int(input())
stable_horses = sorted([0, horse_num + 1] + [int(input()) for _ in range(stable_num)])

"""
lowest_ops[i][j] = min operations if we only consider horses
from that exist in the index interval (i, j)
ex: lowest_ops[1][4] and stable_horses = [0, 1, 3, 7, 10, 11]
	means that we only consider horses from (1, 10)
"""