我跨过忘川，也走过彼岸——《忘川彼岸》

考虑dp，设$ f[x][0/1] $为当前考虑到左岸的第$ x $个村庄，当前村庄有/没有被连接。

枚举$ x $，存一个$ lst $表示现在连到了右岸的第$ lst $个村庄（$ lst $没连）。

$ f[x][1] $有两种转移来源：

• $ f[x][1]=f[lst][1]+dis(x,lst) $
• $ f[x][1]=f[x-1][1]+y1[x]$

时空都是线性的。