Subtask 1

There are many different Dynamic Programming (DP) solutions with $\mathcal{O}(n^2)$ or $\mathcal{O}(n^3)$ running time for this subtask. The simplest one is to define $d{p}_{i,j}$ as the minimum cost needed for wiring the first $i$ red points and the first $j$ blue points. The update is like:

$${\displaystyle d{p}_{i,j}=min(d{p}_{i-1,j},d{p}_{i,j-1},d{p}_{i-1,j-1})+|re{d}_i-blu{e}_j|}$$

Subtask 2

This subtask is to find the pattern of wiring. A simple solution to this subtask is to calculate:

$${\displaystyle \sum _{i=0}^{n-1}(re{d}_{n-1}-re{d}_i)+\sum _{i=0}^{m-1}(blu{e}_i-blu{e}_0)+max(n,m)\times (blue[0]-red[n-1])}$$

Subtask 3

Consider the consecutive clusters of points with the same color. The idea is that each wire will have endpoints in two consecutive clusters, so the $\mathcal{O}(n^2)$ solutions could be optimized to $\mathcal{O}(n\times MaxBlockSize)$.

Subtask 4

This subtask could be solved by a greedy algorithm that divides each cluster into two halves and connects the left half to the left cluster and the right half to the right cluster. The middle point of a cluster with an odd number of points should be considered separately.

Optimal solution

There is an $\mathcal{O}(n+m)$ DP solution: let $d{p}_i$ be the minimum total distance of a valid wiring scheme for the set of point $i$ and all points to the left of it. This could be updated with an $\mathcal{O}(1)$ amortized time complexity.