题目大意
有一个$n \times n$大小的棋盘,棋盘的每个格子上有一个字母(是U,L,R,D,X
中之一),其中U
表示向上走,D
表示向下走,L
表示向左走,R
表示向右走,X
表示走到这个格子就停止。
现在给你$n ^ 2$个坐标$(x_{i,j}, y_{i, j})$表示从$(i, j)$出发能走到的位置(如果无限循环则为$-1$),你需要构造出这个棋盘,或者输出INVALID
,$n \leq 10^3$
斜率优化的练手题
通读题目可以发现
$$
f_i=\max (f_j+g(s[i]-s[j]))
$$
$$
其中f_i表示在i处强制结束一段的最大代价,s_i表示a_i的前缀和,g(x)表示(ax^2+bx+c)
$$
设$f_u$表示$u$不被以$u$为根的子树内点(包括$u$)通上电的概率,则有:
$$f_u=(1-p_u) \times \prod_{v \in subtree \; u}e(u, v) \times f_v$$
Update your browser to view this website correctly. Update my browser now