LOJ2074/2157 JSOI2016/POI2011 Lightning Conductor 决策单调性DP
2024-10-21 09:11:56
我们相当于要求出\(f_i = \max\limits_{j=1}^{n} (a_j + \sqrt{|i-j|})\)。这个绝对值太烦人了，考虑对于\(i>j\)和\(i<j\)分开做。
当\(i>j\)时，\(f_i = \max\limits_{j=1}^{i-1}(a_j + \sqrt{i-j})\)。注意到这是一个典型的\(f_i = \max\limits_{j=1}^{i-1}f_j + w(i,j)\)的形式，考虑决策单调性。不难证明\(\sqrt{x + 1} - \sqrt{x} < \sqrt{x} - \sqrt{x - 1}\)，故对于决策点\(p<q , \sqrt{i+1-p} - \sqrt{i-p} < \sqrt{i+1-q} - \sqrt{i-q}\)，也就是说\(w(i+1,p) - w(i,p) < w(i+1,q) - w(i,q)\)，满足四边形不等式。
那么可以按照传统的方法，在队列中维护决策三元组\((x,l,r)\)表示当\(i \in [l,r]\)时，\(f_i = f_x + \sqrt{i-x}\)，每加入一个新的决策时在队尾弹出被当前决策代替的决策，然后在最后一个有效决策的范围上二分得到当前决策的范围。当有询问时直接拿出队头的答案即可。
最新文章
- PHP相关代码
- STL容器适配器 stack, queue
- Transistor 晶体管 场效应 双极型 达林顿 CMOS PMOS BJT FET
- Asp.net设计模式笔记之二：应用程序分离与关注点分离
- Python快速教程
- 设置 MyEclipse 默认打开文件方式
- 本地连接图标消失；修改地址IP地址
- Com和DCOM
- uva-10487 - Closest Sums
- Csharp多态的实现(抽象类)
- C#处理JSON 数据
- vue2.0+element+node+webpack搭建的一个简单的后台管理界面
- IE不兼容ES6箭头函数的解决方法（在浏览器中使用）
- Codeforces 126B. Password (KMP)
- 使用Python内置浏览器缓存cookies并做更新
- c# ref和out参数
- Linux移植之内核启动过程start_kernel函数简析
- python-观察者模式
- Bootstrap-CL：面板
- 怎样安装Scrapy