注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

poi2011(bzoj 2216) Lightning Conductor  

2013-04-01 17:50:43|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这是一个非常经典的模型了,1D1D的动态规划
这类问题最基础的是斜率优化。难一点的就很麻烦了……什么用平衡树维护凸包之类的。不过我完全不会
这题是我见到的第一道非斜率优化的1D1D了……

F[i]=max{a[j]+sqrt(abs(i-j))}-a[i]
以下均建立在j<i的基础上的
注意到函数f(x)=sqrt(x)-sqrt(x-1)单调递减,所以若k<j<i且对于i而言j比k优,则k没用了
然后可以yy出很多东西
比如对于i,最优解是i的必然是一段区间。
所以我们维护一个栈,栈里每一个元素都代表一段区间,表示这段区间的最优解都来自这个元素p。所以一个元素是个三元组(p,l,r)
要保证对于i最优决策是队首区间
然后插入i,如果他能改变队列的情况,那么i对应的区间必然是[l,n]
所以步骤如下:
    如果对于n,当前的i比队尾更优,就不断的将队尾区间弹出栈。将区间(p,l,r)弹出来的条件是对于l,i比p更优。
    现在我们的队尾(p,l,r)满足,对于l,p比i优;对于r,i比p优。我们可以通过二分查找,找到一个临界点q,然后将队尾变成(p,l,q-1)并将元素(i,q+1,n)插入队尾
    这只是大概思路,实现过程中要注意队列为空
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define Rep(i,l,r) for(int i=l;i<=r;i++)
#define MAXN 500010
#define eps 1e-13
using namespace std;
int dcmp(double p)
{
if(fabs(p)<eps) return 0;
return p>eps?1:-1;
}
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
struct Node
{
int id,l,r;
Node() {}
Node(int id,int l,int r): id(id),l(l),r(r) {}
};
int n,digit[MAXN];
double F[MAXN],G[MAXN];
double calc(int i,int j){ return digit[j]+sqrt(abs(i-j)); }
void read()
{
Read(n);
Rep(i,1,n) Read(digit[i]);
}
int Find(int l,int r,int p,int q)
{
while(l<r)
{
int mid=(l+r)>>1;
if(calc(mid,p)<calc(mid,q)) l=mid+1;
else r=mid;
}
return l;
}
void Dp(double ans[])
{
static Node queue[MAXN];
int front=1,rear=0;
Rep(i,1,n)
{
if(front<=rear&&++queue[front].l>queue[front].r) front++;
if(front>rear||calc(n,i)>calc(n,queue[rear].id))
{
while(front<=rear&&calc(queue[rear].l,i)>calc(queue[rear].l,queue[rear].id)) rear--;
if(front>rear) queue[++rear]=Node(i,i,n);
else
{
int p=Find(queue[rear].l,queue[rear].r,i,queue[rear].id);
queue[rear].r=p-1,queue[++rear]=Node(i,p,n);
}
}
ans[i]=calc(i,queue[front].id);
}
}
int main()
{
read();
Dp(F);
reverse(digit+1,digit+n+1);
Dp(G);
reverse(digit+1,digit+n+1);
reverse(G+1,G+n+1);
Rep(i,1,n) printf("%d\n",(int)ceil(max(F[i],G[i])-digit[i]));
return 0;
}


  评论这张
 
阅读(1182)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017