12170

UVA12170 7 月份的题了，补一补。场上写挂了一点还是很遗憾的。 容易想到 dp。 但是由于值域非常大，直接 dp 是不行的。但是 \(n\) 非常小，容易想到离散化。 但是离散化后是不能直接加减的。有用的数值初看是有 \(\mathcal{O}(n^2d)\) 的，即 \(h_i + kd( ......

从另一个网站上的我的博客里转的。感觉放在一起比较好。时间久远，而且是英文（流泪）。 # [Easy Climb](https://www.luogu.com.cn/problem/UVA12170) ## Step 1 If $x_i,d\le 100$. Then define $dp_{i,j} ......