昨晚 CF G

userId_undefined
cjdst
小有名气尊贵铂金CSP-S一等奖

2026-07-15 10:19:24

发布于：广东

24阅读
0回复
0点赞

我好区，被六年级 xxs 单调队列了。

场上思路：

考虑“拉”与“推”DP 结合。

  • 拉：dpi=max⁡{推的贡献,max⁡1≤j<i−Ai且Aj≤Aidpj}+Aidp_i=\max\{推的贡献,\max_{1\le j\lt i-A_i且A_j\le A_i} dp_j\}+A_i。
  • 推：将 dpidp_i 值贡献到所有 j>i+Aij\gt i+A_i 且 Aj≤AiA_j\le A_i 的 jj 上。

显然都是二维偏序，而且要动态更新所以是在线的，然后有一些很紫的 O(nlog⁡2n)O(n\log^2 n) 做法。

事实上，“推”DP 完全可以放到“拉”DP 转移。就是考虑转移 dpidp_i 时，查询 max⁡1≤j<i−Ai且j+Aj<i\max_{1\le j\lt i-A_i且j+A_j\lt i} 即可，不需要推。可以看作在线单点改 (i,i+Ai)(i,i+A_i)，矩形查 ([1,i−Ai−1],[1,i−1])([1,i-A_i-1],[1,i-1])。由于【数据删除，我也不知道为啥】，所以这其实是离线二维数点？？？O(nlog⁡n)O(n\log n)。

这显然是对的，但这为啥是对的，这显然是对的，但这为啥是对的，这显然是对的，但这为啥是对的，这显然是对的，但这为啥是对的，这显然是对的，但这为啥是对的，

userId_undefined
去预览
0/2000

全部评论 3

  • userId_undefined
    Xylophone
    传道者

    你怎么偷偷去集训了👊

    2026-07-15 来自 广东

    0
  • userId_undefined
    Xylophone
    传道者

    咦这个有意思

    2026-07-15 来自 广东

    0
  • userId_undefined
    cjdst
    小有名气尊贵铂金CSP-S一等奖

    d

    2026-07-15 来自 广东

    0

热门讨论