19.9.24 CSP->省选模拟赛

T1

水题。然而写挂了。对于两个点分类讨论即可，不说了。

T2

发现式子的含义，即在一个每一列$i$的每一行值都是$y_i$的方格图上，从点$(x,y)$走到$x$为$1$的地方，要求路上经过的值之和最小。 冷静分析一下，可以发现，走法一定是向左上方走一段，然后直着上去。 令$g_{y,j}(x)$，表示从$(x,y)$走到$(1,j)$，最后那一段直着上去的在$j$的答案。 $$g_{y,j}(x) = sum_y - sum_j + A_j (x - y + j)$$ $$f_{x,y} = \min g_{y,j}(x)$$ 容易发现，把$g$看作直线，最优答案一定在上凸壳的边上。如果维护出了所有的$g$，就可以斜率优化了。 考虑如何$g_{y,j} \rightarrow g_{y + 1, j}$ $$g_{y + 1, j} = sum_y + A_{y + 1} - sum_j + A_j (x - y + j - 1)$$ 其实就是把原来所有的线向右平移一格，向上平移$A_{y + 1}$格。 再考虑新加入的直线表达式到底是什么： $$g_{y + 1, y + 1} = sum_{y + 1} - sum_{y + 1} + A_{y + 1} (x - (y + 1) + (y + 1)) = A_{y + 1} x$$ 上面得出的性质是很好的。它告诉我们，每次$y+1$的时候，原来的凸壳移动了一些，同时加入了一条过原点的线。新的线加在了原来凸壳的左边。 那么如何维护这个上凸壳就很显然了：

1. 弹掉所有斜率比它大的线
2. 弹掉使得相邻直线交点不单调的线

对蒟蒻来说好难啊OAO 乱码了，点这里看代码

T3

暴力比较显然，正解不会，先咕咕了