首先简化问题很明显,每组有用的只有前缀最大值。 先想想贪心,不可做,因为一组的贡献会被其他组影响,所以考虑 \texttt{dp} 组与组之间无序,不能沿编号轴 \texttt{dp} ,考虑值域轴,每接上一个组只需要考虑当前最大值,且较大最大值一定由较小最大值转移而来,所以设 f_i 表示当前最大
你谷传送门 非常 OI 的一道题 看到这题就往图论的方向去想了,但其实能看出本质与竞赛图有关的话甚至能更快,只可惜事先没有接触过,敏感度不够。 往正常方向推也挺好推的,但其实我在第一步就炸了,我考虑的是怎么利用整个排名表的信息维护一位选手的答案 傻逼吗我是 ,这里两者信息完全不对等,大量信息被浪费。
题目传送门 代码实现和一些思路参考了一些题解。 遇到这种序列上研究大小的序列问题,应该主动考虑笛卡尔树。 对原序列建出一棵大根笛卡尔树。稍微转化一下问题的连边条件,首先每个节点必定和它的左子树同在所有点在同一个连通块,这样初步连边后可以看出连通块与连通块之间通过树上右链(从根一直向右走的链)的边进行