Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

Solution [USACO21JAN] Minimum Cost Paths P

posted on 2021-08-18 19:19:02 | under 题解 |

Description

给你一张 $n\times m$ 的网格图,从 $(1,1)$ 出发,有如下两种移动方式:

  1. 从 $(x,y)$ 移动到 $(x,y+1)$,代价为 $x^2$。

  2. 从 $(x,y)$ 移动到 $(x+1,y)$,代价为 $c_y$。

现在给出 $q$ 组询问 $(x,y)$,求从 $(1,1)$ 走到 $(x,y)$ 的最小代价。

Constraint

见原题

Solution

首先感谢 @CXY07,他教会了我这道题的解法。

设在第 $i$ 列我们从 $(s_{i-1},i)$ 移动到了 $(s_i,i)$($s_0=0$),那么总代价为$$\sum_{i=1}^{y-1}[s_i^2+(s_i-s_{i-1})c_i]+(x-s_{y-1})c_y$$

作一些变形可得$$ \begin{aligned} \sum_{i=1}^{y-1}[s_i^2+(s_i-s_{i-1})c_i]+(x-s_{y-1})c_y&=\sum_{i=1}^{y-1}\left[s_i^2+s_i(c_i-c_{i+1})\right]+(xc_y-c_1)\\ &=\sum_{i=1}^{y-1}\left(s_i-\frac{c_{i+1}-c_i}{2}\right)^2-\sum_{i=1}^{y-1}\frac{(c_i-c_{i+1})^2}{4}+(xc_y-c_1) \end{aligned} $$ 忽略常数项,我们发现要做的仅仅是$$\begin{aligned}&\operatorname{minimize }\sum_{i=1}^{y-1}\left(s_i-\frac{c_{i+1}-c_i}{2}\right)^2\\&\operatorname{s.t. }s_i\le s_{i+1},1\le s_i\le x,s_i\in \mathbb N_{+}\end{aligned}$$ 这是经典的保序回归问题,翻阅 2018 年的国家预选队论文即可知道做法。

并且注意到 $\dfrac{c_{i+1}-c_i}{2}$ 这种差分形式的前缀和非常好维护。