BOJ 19545
This is an interesting DP problem.
Problem
The problem is to place $N+M-1$ edges in a bipartite graph with $N, M$ vertices such that the sum of distances between all pairs of vertices is minimized. Since it must be a connected graph and edges cannot overlap, only special forms of graphs are possible.
Analysis
If we think of connecting edges from the upper vertices to the lower vertices, they must be connected to vertices in consecutive intervals, and the intervals must share their endpoints. In other words, if we create edges from the $i$-th vertex above to vertices from $s_i$ to $e_i$ below, the following conditions must be satisfied.
\[e_i=s_{i+1} \, (0 \leq i < N-1)\] \[s_0 = 0, \, e_{N-1} = M-1\]If we create an edge between the $i$-th vertex above and the $j$-th vertex below, the weight (distance) can be calculated as follows:
\[dis_{i, j}=(U_i - D_j)^2 + L^2\]Since the $i$-th vertex above creates edges from $s_i$ to $e_i$ below, $j$ below satisfies $(s_i \leq j \leq e_i)$. Since we need to minimize the sum of distances between all vertices, we can calculate the sum of distances by multiplying the number of times each vertex is used by the weight of the edge.
If we draw the graph and calculate, the distance added when connecting the $i$-th vertex above and the $j$-th vertex below is as follows:
Now we need to divide the $M$ vertices below into $N$ intervals $(s_0, e_0),…,(s_{N-1}, e_{N-1})$ such that the sum of $C_{i, j}$ is minimized.
Solution
Define $dp_{i, j}$ as the minimum sum of distances when up to the $i$-th vertex above and up to the $j$-th vertex below satisfy the condition (connected graph with no overlapping edges), and the $i$-th vertex above is connected to the $j$-th vertex below. We increase $i$ from $0$ to $N-1$ and calculate $dp_{i, j}$ for all $j$. The value is transitioned as follows:
\[dp_{i, j} = \min\limits_{k \leq j} \Big(dp_{i-1, k} + \sum\limits_{l=k}^{j} C_{i, l} \Big)\]The $i$-th vertex above will connect edges to the interval $(s_i, e_i)=(k, j)$ below. The time complexity at this point is $O(N M^2)$, so an additional idea is needed.
Optimization
$C_{i, l}$ is tricky because when it’s at both ends of the interval $\text{$l=k$ or $l=j$}$, it’s calculated differently as $f(i, l)$.
However, if the original interval has length $2$ or more, fixing the left endpoint and extending only the right endpoint by $1$ is straightforward. That is, if the interval $(k, j-1)$ becomes $(k, j)$, we can easily calculate it by adding $f(i, j) - f(i, j - 1) + g(i, j - 1)$.
Therefore, when updating $dp_{i, j}$, we can speed this up by maintaining the minimum value for positions up to $j-1$ where the last interval has length at least $2$.
$x$ maintains the minimum value for intervals of length $2$ or more. $c_1$ extends $x$’s interval by $1$, so it handles intervals of length $3$ or more; $c_2$ handles intervals of length $2$; and $c_3$ handles intervals of length $1$. When updating $dp_{i, j}$, we take the minimum among these three cases. This optimization reduces the time complexity to $O(NM)$. Below is the implementation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cache[3000];
ll N, M, L;
ll U[3000], D[3000];
ll dis[3000][3000];
const ll MAX = 1e17;
ll f(ll i, ll j) { return dis[i][j] * (i + j + 1) * (M + N - i - j - 1); }
void solve() {
cin >> N >> M >> L;
for (int i = 0; i < N; ++i) cin >> U[i];
for (int i = 0; i < M; ++i) cin >> D[i];
for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) {
dis[i][j] = (U[i] - D[j]) * (U[i] - D[j]) + L * L;
}
for (int i = 0; i < M; ++i) cache[i] = MAX;
cache[0] = 0;
ll ncache[3000];
for (int i = 0; i < N; ++i) {
ll x = MAX;
for (int j = 0; j < M; ++j) {
ll c1, c2, c3;
if (j != 0) c1 = x - f(i, j - 1) + dis[i][j - 1] * (M + N - 1) + f(i, j);
else c1 = MAX;
if (j != 0) c2 = f(i, j - 1) + f(i, j) + cache[j - 1];
else c2 = MAX;
c3 = cache[j] + dis[i][j] * (M + N - 1);
ncache[j] = min({c1, c2, c3});
x = min(c1, c2);
}
swap(ncache, cache);
}
cout << cache[M - 1];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
}
The official solution converts this to paths on a grid, which is quite elegant. You can see that it’s essentially equivalent to managing intervals. I used an alternative approach by maintaining cases where the last interval has length at least $2$, while the official solution incorporates the direction of movement on the grid directly into the DP state. I wrote this article because my solution differs from the official one, but I recommend reading the official editorial as well.