[BZOJ2216]Lightning Conductor
原来决策单调性指的是这个东西...
一些DP可以写成$f_i=\max\limits_{j\lt i}g(i,j)$,设$p_i(p_i<j)$表示使得$g(i,j)$最大的$j$,如果$p_1\leq\cdots\leq p_n$,那么我们称这个DP满足决策单调性,称$p_i$为$i$的最优决策点
决策单调性可以用整体二分来做,设当前要处理$f_{l\cdots r}$且最优决策点的范围是$[h,t]$,那么我们先求出$f_{mid}$,这个直接暴力从$\left[h,\min(mid,t)\right]$转移即可,假设$mid$的最优决策点是$d$,那么我们可以递归做$(l,mid-1,h,d)$和$(mid+1,r,d,t)$,二分总共$O(\log_2n)$层,每一层最多$O(n)$,总时间复杂度$O\left(n\log_2n\right)$
这题的DP方程是$f_i=\max\{a_j+\sqrt{\left|i-j\right|}\}-a_i$,为了把绝对值去掉,我们作限制$j\lt i$,正反各做一遍取最大值即可
$f_i=\max\limits_{j\lt i}\{a_j+\sqrt{i-j}\}-a_i$
设$i$的最优决策点为$p$,那么对于$\forall k\lt p$有$a_k+\sqrt{i-k}\leq a_p+\sqrt{i-p}$
因为$\sqrt{x+1}-\sqrt x$是单调递减的,所以$\sqrt{i+1-k}-\sqrt{i-k}\leq\sqrt{i+1-p}-\sqrt{i-p}$
把它加到上面,我们得到$a_k+\sqrt{i+1-k}\leq a_p+\sqrt{i+1-p}$
这也就说明了$i+1$的最优决策点$\geq p$,也就是说这个DP满足决策单调性
#include<stdio.h> #include<math.h> typedef double du; du max(du a,du b){return ceil(a>b?a:b);} void swap(int&a,int&b){ int c=a; a=b; b=c; } int a[500010]; void solve(du*f,int l,int r,int h,int t){ if(l>r||h>t)return; int mid,i,d; du res=-2147483647.; mid=(l+r)>>1; for(i=h;i<=t&&i<=mid;i++){ if(a[i]+sqrt(mid-i)>res){ res=a[i]+sqrt(mid-i); d=i; } } f[mid]=res-a[mid]; solve(f,l,mid-1,h,d); solve(f,mid+1,r,d,t); } du f[500010],g[500010]; int main(){ int n,i; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",a+i); solve(f,1,n,1,n); for(i=1;i<=n>>1;i++)swap(a[i],a[n-i+1]); solve(g,1,n,1,n); for(i=1;i<=n;i++)printf("%.0lf\n",max(f[i],g[n-i+1])); }
最新文章
- kubernetes&;tensorflow
- iconv 失败
- Editor扩展之查看Prefab用在那儿
- 【20140113-2】MyEclipse生成javadoc时出错:编码GBK的不可映射字符
- .net后台获取HTML中select元素选中的值
- MetaPhlAn 2:宏基因组进化分析
- EF实体框架之CodeFirst五
- 浅谈Java对象回收的三种方式
- CodeForces 754D Fedor and coupons (优先队列)
- sqlserver2014无法打开报Cannot find one or more components_修复方案
- 2018.9.12 B树总结
- Vue(四)之webpack和vue-cli
- [luogu3369][普通平衡树]
- EntityFramework扩展之第三方类库
- pyCharm的第一个项目
- How to use “cat” command on “find” command&#39;s output?
- Guava的RateLimiter在单机限流中的正确用法
- 洛谷 P3159(BZOJ 2668)[CQOI2012]交换棋子
- TensorFlow saved_model 模块
- RHEL7虚拟机添加新网卡后,网卡无法启动