题目链接

题意:已知一个长度为 n 的序列 a。对于每个 1<=i<=n,找到最小的非负整数 p 满足 对于任意的 j, aj < = ai + p - sqrt(abs(i-j))


已经懒到不想打数学公式了...

差不多是第一次写这种决策单调性的题,怎么弱成这个样子啊... 所以写的详细一点。

首先取绝对值很烦,显然我们可以正反各做一遍,拿掉绝对值。

令 \(f_i=max(a_j+\sqrt{i-j})-a_i\)

把这个看成 dp,则满足如下性质:

对于本层(本题只有一层)dp,求一点的 dp 值与同层其他点均无关。(显然得证)

令\(f_i\) 的决策点为\(opt_i\),则一定有\(opt_1\leq opt_2\leq ...\leq opt_n\)(证明非常简单,考虑一个 opt_{i} > opt_{i+1} 的情况,显然不成立)

那么我们可以分治优化这层的 dp 过程,每次维护可能取值的区间,取出 mid 切割区间即可,\(log_n\) 层,每层\(O(n)\),复杂度\(O(nlog_n)\)

 

 


一个非常弱的准退役OIER