题解：P12585 「KTSC 2019 R1」广播站

· · 题解

5 个 dp 数组的来了

首先，我们考虑如果一个广播站传播半径为 r，那么一定可以给这个广播站定一个唯一的方向，即选定另一个广播站在半径范围内，使得每次经过前者时一定会跳到后者。这样显然可以做到，因为如果我们设 dist_u 表示 u 传播到汇点的最小次数，那么每次经过一个广播站时只要走向半径范围内 dist 值最小的点即可。

定向后，每个点的出度最多为 1。又由于汇点没有出边，因此为了保证所有点都能到达汇点，除了汇点以外的所有点出度均为 1。记 u 的唯一的出边指向 v，则总代价即为 \sum\limits_{(u,v)}(x_u-x_v)^2。同时，定向后对于 u 的唯一的出边指向 v，有 dist_u=dist_v+1。

考虑最优化答案的情况下图的形态（建议手玩一下，感性理解也可以）。

如果存在 a<b<c<d,a\to c,d\to b

考虑 x 为 b,c 中 dist 值较小的点（相同则任意），另一个点为 y，那么将两条边中指向 y 的边指向 x，不仅不会增加任何 dist 值，还一定可以减小总代价。因此这样的情况不会出现。

如果存在 a<b<c<d,c\to a,b\to d

  1. 若 dist_b\ne dist_c，那么 类似地设 x 为 b,c 中 dist 值较小的点，另一个点为 y，那么将 y 指向 x，也一定不会变劣，且总代价会减小。因此这样的情况不会出现。
  2. 若 dist_b=dist_c，则 dist_a+1=dist_d+1，因此 dist_a=dist_d。此时 c\to a,b\to d 就等价于 b\to a,c\to d。直接改为后者一定不会变劣，且总代价会减小。因此这样的情况不会出现。

如果存在 a<b<c<d,a\to c,b\to d

  1. 若 dist_c\le dist_d，此时将 b\to d 改为 b\to c，不会变劣，总代价减小。因此这样的情况不会出现。
  2. 若 dist_c>dist_d，此时 dist_c\ge dist_d+1=dist_b，那么将 a\to c 改为 a\to b，不会变劣，总代价减小。因此这样的情况不会出现。

如果存在 a<b<c<d,c\to a,d\to b

上面情况对称一下，同理。

因此，我们得出重要结论：不可能存在两条交叉（包含或共端点不算）的边，即不可能存在 a<b<c<d 使得 a,c 间有边，b,d 间也有边。

同时，我们如果已经确定了汇点的位置，那么就不可能有边越过汇点连接，即不存在 a<x<b 使得 a,b 间有边，其中 x 为汇点。这也很显然：如果我们都能从汇点的一侧连到另一侧，还不如直接连向汇点，这样会减小总代价且减小该边起点的 dist 值。

这启发我们对于汇点两侧分别考虑，因为两侧之间互不影响。而数据范围可以让我们想到高次多项式时间复杂度，因此考虑 dp。在 dp 的过程中，我们发现可能整个序列前后缀的 dp 值与某一段非前后缀的 dp 值有关，因此考虑区间 dp。

设

l 的转移

定向后，一定存在 [i+1,j] 中的点使得这个点连向 i。考虑找出最大的这样的点，记为 k。那么由于不存在交叉边，则 [k+1,j] 中的点不会连向 k 左边。而 [k+1,j] 中的点最终仍要到达 i，那么就只能通过 k\to i 来到达 i。

因此 [i+1,k-1] 的定向与 [k+1,j] 的定向就变成了两个独立的子问题。左半部分由于已经确定了 k\to i，且限制为走到 i 点的距离 \le d，因此符合 L_{i,k,d} 的定义。右半部分一定要经过 k\to i，那么走到 i 的距离 \le d 的限制就相当于走到 k 的距离 \le d-1 的限制，符合 l_{k,j,d-1} 的定义。最后，k\to i 的代价为 (x_k-x_i)^2。所以转移式即为

l_{i,j,d}=\min_{k=i+1}^jL_{i,k,d}+l_{k,j,d-1}+(x_k-x_i)^2

r 的转移

同理，

r_{i,j,d}=\min_{k=i}^{j-1}r_{i,k,d-1}+R_{k,j,d}+(x_j-x_k)^2

L 的转移

同样地，设 k 为 [i+1,j-1] 内最大的连向 i 的点。如果没有这样的点，令 k=i。那么 [k+1,j-1] 内的点不可能连向 k 左边。

那么 [i+1,k-1] 的定向与 [k+1,j-1] 的定向就变成了两个独立的子问题。左半部分由于已经确定了 k\to i，且限制到 i 的距离 \le d，符合 L_{i,k,d} 的定义。由于有 k\to i,j\to i，右半部分 [k+1,j-1] 此时一定要经过 k\to i,j\to i 中的一条边到达 i，也就是先要到达 k,j 中的一个，且限制到该点的距离 \le d-1，这恰好就是 f_{k,j,d-1}。最后，k\to i 的代价为 (x_k-x_i)^2。

当 k=i 时，那么只有 j\to i 一条边。此时 [j+1,i-1] 中的点一定要经过 j\to i 才能到达 i，也就是说要先到达 j，且限制到 j 的距离 \le d-1，符合 r_{i+1,j,d-1} 的定义。但我们发现 r_{i+1,j,d-1} 被 f_{i,j,d-1} 完全包含（后者限制更松，如果可以到达 j，就一定可以到达 i,j 之一），而 f_{i,j,d-1} 被 L_{i,j,d} 包含（如果在 d-1 步内到达了 j，那么再通过 j\to i 就可以再 d 步内到达 i）。所以如果我们令 L_{i,k,d}=0，那么上述转移仍然成立。综上，转移式即为

L_{i,j,d}=\min_{k=i}^{j-1}L_{i,k,d}+f_{k,j,d-1}+(x_k-x_i)^2

R 的转移

同理，

R_{i,j,d}=\min_{k=i+1}^jf_{i,k,d-1}+R_{k,j,d}+(x_j-x_k)^2

f 的转移

考虑对于 i<a<b<j，是否可能有 a 最终到达 j，b 最终到达 i。如果 a,b 分别到达各自的目的地的路径有交点，那么由于任意点的出度至多为 1，不可能最终到达的点不同。所以 a,b 分别到达各自的目的地的路径上一定没有交点。

设 a 到 j 的路径为 a=u_1\to u_2\to\dots\to u_p=j，b 到 i 的路径为 b=v_1\to v_2\to\dots\to v_q=i，那么找到第一个 k 使得 u_{k+1}>b。这样的 k 一定存在，因为 u_p=j>b。所以我们就有边 u_k\to u_{k+1} 且 u_k\le b,u_{k+1}>b。由于路径无交，有 u_k\ne b,u_k\ne i，因此 i<u_k<b,b<u_{k+1}。而 b 到 i 的路径又不经过 u_k 或 u_{k+1}，那么能到达 i 一定存在一条路径上的边从 [u_k+1,u_{k+1}-1] 内的点连向外面的点，而这条边本身就与 u_k\to u_{k+1} 交叉，与之前的不存在交叉的条件矛盾。

因此，不存在 i<a<b<j 使得 a 最终到达 j，b 最终到达 i。那么就一定存在一个点 k，使得 [i+1,k] 内的点最终到达 i，[k+1,j-1] 内的点最终到达 j。而左半部分的点不可能连向右半部分（如果连向右半部分，那么该点就会到达右部分，最终到达 j），有半部分的点也不可能连向左半部分。那么 [i+1,k] 的定向与 [k+1,j-1] 的定向就变成了两个独立的问题，左半部分即 l_{i,k,d}，右半部分即 r_{k+1,j,d}。综上，转移式即为

f_{i,j,d}=\min_{k=i}^{j-1}l_{i,k,d}+r_{k+1,j,d}

时间复杂度 O(n^4)。注意，转移要按照 f,L,R,l,r 的顺序，因为后者可能会依赖于前者的答案。 :::info[代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 121;
int n, x[N], l[N][N][N], r[N][N][N];
int L[N][N][N], R[N][N][N], f[N][N][N];
inline int w(int a) { return a * a; }
void stations(vector <signed> X);
void answer(vector <int> Ans);
void stations(vector <signed> X) {
    n = X.size();
    for (int i = 1; i <= n; i++) x[i] = X[i - 1];
    memset(l, 0x3f, sizeof(l)), memset(r, 0x3f, sizeof(r));
    memset(f, 0x3f, sizeof(f)), memset(L, 0x3f,
    sizeof(L)), memset(R, 0x3f, sizeof(R));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++) l[i][i][j] = r[i][i][
        j] = L[i][i][j] = R[i][i][j] = f[i][i][j] = 0;
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            if (len == 2) f[i][j][0] = 0;
            for (int p = i; p < j; p++)
                for (int k = 1; k <= len; k++)
                    f[i][j][k] = min(f[i][j][k],
                    l[i][p][k] + r[p + 1][j][k]);
            for (int p = i; p < j; p++)
                for (int k = 1; k <= len; k++)
                    L[i][j][k] = min(L[i][j][k], L[i][p][
                    k] + w(x[p] - x[i]) + f[p][j][k - 1]);
            for (int p = i + 1; p <= j; p++)
                for (int k = 1; k <= len; k++)
                    R[i][j][k] = min(R[i][j][k], R[p][j][
                    k] + w(x[j] - x[p]) + f[i][p][k - 1]);
            for (int p = i + 1; p <= j; p++)
                for (int k = 1; k <= len; k++)
                    l[i][j][k] = min(l[i][j][k], L[i][p][
                    k] + w(x[p] - x[i]) + l[p][j][k - 1]);
            for (int p = i; p < j; p++)
                for (int k = 1; k <= len; k++)
                    r[i][j][k] = min(r[i][j][k], r[i][p][
                    k - 1] + w(x[j] - x[p]) + R[p][j][k]);
            for (int k = len + 1; k <= n; k++) l[i][j][k] =
            l[i][j][k - 1], r[i][j][k] = r[i][j][k - 1],
            L[i][j][k] = L[i][j][k - 1], R[i][j][k] =
            R[i][j][k - 1], f[i][j][k] = f[i][j][k - 1];
        }
    vector <int> res(n - 1);
    for (int i = 1; i < n; i++) {
        int ans = 2e18;
        for (int j = 1; j <= n; j++)
            ans = min(ans, r[1][j][i] + l[j][n][i]);
        res[i - 1] = ans;
    }
    answer(res);
}

:::