P7297 [USACO21JAN] Telephone G

Farmer John 的 N 头奶牛，编号为 $1…N$，站成一行（$1≤N≤5⋅10^4$）。第 $i$ 头奶牛的品种编号为 $b_i$，范围为 $1\dots K$，其中 $1≤K≤50$。奶牛们需要你帮助求出如何最优地从奶牛 $1$ 传输一条信息到奶牛 $N$。 从奶牛 $i$ 传输信息到奶牛 $j$ 花费时间 $|i-j|$。然而，不是所有品种的奶牛都愿意互相交谈，如一个 $K\times K$ 的方阵 $S$ 所表示，其中如果一头品种 $i$ 的奶牛愿意传输一条信息给一头品种 $j$ 的奶牛，那么 $S_{ij}=1$，否则为 $0$。不保证 $S_{ij}=S_{ji}$，并且如果品种 $i$ 的奶牛之间不愿意互相交流时可以有 $S_{ii}=0$。 请求出传输信息所需的最小时间。

无

无

最优传输序列为 $1\to 4\to 3\t 5$。总时间为 $|1-4|+|4-3|+|3-5|=6$。 #### 测试点性质： - 测试点 1-5 满足 $N≤1000$。 - 测试点 6-13 没有额外限制。 供题：Dhruv Rohatgi