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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【研究了一天半的】[HNOI2008]玩具装箱toy && 斜率优化  

2014-04-09 17:21:35|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@BZOJ1010:[HNOI2008]玩具装箱toy

昨天下午研究了“一下”斜率优化

其实本来听明白过,但是现在一看又有点晕……于是我就问GTY神犇……然后越问越晕……最后干脆去问wzy神犇。

后来又去问wangxz神犇三分,把神犇惹烦了QAQ对不起

然后……我就研究了斜率优化研究了一天半QAQ我好弱

今天下午总算把这个题A了

GTY神犇研究了一下午就研究明白,俺看了一天半……

扔一下代码:

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
deque <int> dui;
const int N = 50001;
typedef long long LL;
int n,m;
LL L,C,ci[N],sum[N],a[N],f[N];
LL pow2(long long d){return d*d;}
LL Dx(int k,int j){return a[k]-a[j];}
LL Dy(int k,int j){return (pow2(a[k]+C)+f[k])-(pow2(a[j]+C)+f[j]);}
//1-> j优于k 0->k优于j (k<j)
short cmp(int k,int j,int i){if(Dy(k,j)>=2*a[i]*Dx(k,j)) return 1;return 0;}
//while Dy(k,j)/Dx(k,j) <= Dy(j,i)/Dx(j,i)
short cmp2(int k,int j,int i){ return Dy(k,j)/Dx(k,j) >= Dy(j,i)/Dx(j,i); }
int main(){
int i,j;
scanf("%d%d",&n,&L);
for(i=1;i<=n;i++){
scanf("%d",&ci[i]);
sum[i]=sum[i-1]+ci[i];
a[i]=sum[i]+i;
}
C = L+1;
dui.push_front(0);
for(i=1;i<=n;i++){
int now,s;
while(dui.size()>1&&cmp(dui[0],dui[1],i))
dui.pop_front();
now = dui.front();
f[i] = pow2(a[i]-a[now]-C)+f[now];
while((s=dui.size())>1 && cmp2(dui[s-2],dui[s-1],i) )
dui.pop_back();
dui.push_back(i);
}
printf("%lld",f[n]);
return 0;
}

然后是蛋疼的推♂倒过程:

1.
f[i]=(i-j+(sum[i]-sum[j-1])-L)^2+f[j-1]
=(i-(j-1)-1+(sum[i]-sum[j-1])-L)^2 +f[j-1]
=((i+sum[i])-((j-1)+sum[(j-1)])-(L+1))^2 +f[j-1]





a[i]=i+sum[i]
C = L+1

f[i]=(a[i]-a[j-1]-C)^2+f[j-1]
f[i]=(a[i]-a[j]-C)^2+f[j]

2.
设对于状态i的两个决策k,j(k<j)有j优于k -> (a[i]-a[j]-C)^2+f[j]<=(a[i]-a[k]-C)^2+f[k]
那么需要证明对于另外一个状态L(L>I)一定也有决策j优于决策k
(一个决策如果有存在意义,那么就是他的决策比较靠后(不是最优)或者是比较优的(可以比较靠前))
所以有用的决策就可以看成一个单调递减的序列

即证:
(a[L]-a[j]-C)^2+f[j]<=(a[L]-a[k]-C)^2+f[k]

因为a[i]单调递增
所以有a[L] = a[I] + B

(a[i]+B-a[j]-C)^2+f[j]<=(a[i]+B-a[k]-C)^2+f[k]
(a[i]-a[j]-C+B)^2+f[j]<=(a[i]-a[k]-C+B)^2+f[k]
(a[i]-a[j]-C)^2+2*B*(a[i]-a[j]-C)+B^2+f[j]<=(a[i]-a[k]-C)^2+2*B*(a[i]-a[k]-C)+B^2+f[k]
(a[i]-a[j]-C)^2+2*B*(a[i]-a[j]-C)+f[j]<=(a[i]-a[k]-C)^2+2*B*(a[i]-a[k]-C)+f[k]
(a[i]-a[j]-C)^2+f[j]+2*B*(a[i]-a[j]-C)<=(a[i]-a[k]-C)^2+f[k]+2*B*(a[i]-a[k]-C)
(a[i]-a[j]-C)^2+f[j]+2*B*(a[i]-a[j]-C)<=(a[i]-a[k]-C)^2+f[k]+2*B*(a[i]-a[k]-C)

由已知得到:
2*B*(a[i]-a[j]-C)<=2*B*(a[i]-a[k]-C)
-a[j]<= -a[k]
a[j] => a[k]
以为a[i]递增,所以得证

看起来只要用单调队列维护就行了……
……真的行么?
仔细想一下,你会发现随着状态i的后推,单调队列中的东西可能已经不是单调了……
那么怎么办……
用斜率优化!


3.
设决策j优于决策k ,且 j>k
(a[i]-a[j]-C)^2+f[j]<=(a[i]-a[k]-C)^2+f[k]
(a[i]-(a[j]+C))^2+f[j]<=(a[i]-(a[k]+C))^2+f[k]

展开

a[i]^2-2*a[i]*(a[j]+C)+(a[j]+C)^2 +f[j] <= a[i]^2-2*a[i]*(a[k]+C)+(a[k]+C)^2 +f[k]
-2*a[i]*(a[j]+C)+(a[j]+C)^2 +f[j] <= -2*a[i]*(a[k]+C)+(a[k]+C)^2 +f[k]
2*a[i]*(a[k]+C)-2*a[i]*(a[j]+C)+ <= + ((a[k]+C)^2 +f[k]) - ((a[j]+C)^2 +f[j])
2*a[i]*( (a[k]+C) - (a[j]+C) ) <= ( ((a[k]+C)^2 +f[k]) - ((a[j]+C)^2 +f[j]) )
2*a[i]*( a[k] - a[j] ) <= ( ((a[k]+C)^2 +f[k]) - ((a[j]+C)^2 +f[j]) )
xj = a[j] yj = (a[j]+C)^2 +f[j]
(xk-xj)*2*a[i] <= (yk-yj)


又因为xj关于j递增,所以可以得到xj>xk

2*a[i] => (yk-yj) / (xk-xj)

把(yk-yj) / (xk-xj)记为cmp(j,k)
(两个点如果cmp(j,k)小于2*a[i]则说明j这个点优;如果一个位置又靠前又不优,那么在以后的状态也不会是最优决策,所以可以直接去掉它;而如果一个点不够优,但它是新加入的,那么有可能它随着)



Dy(k,j) = yk-yj Dx(k,j) = xk-xj
则对于两个决策位置j,k(j>k)
如果满足
Dy(k,j)*2*a[i] <= Dx(k,j)
就有
决策j优于决策k


不能用单调队列是因为随着状态的后推,原本维护的单调队列不能保证还是一个单调队列。
而此时,你发现,j&k已经脱离i的影响了!也就是说随着状态的后推,维护的凸壳可以保证依旧是一个凸壳(斜率k单调)
然后又因为查询是单调的,并且每次加入点的位置xi = a[i] = sum[i]+i 也是单调的,所以可以用一个单调队列维护,每次用O(1)找到最决策和放入新的决策。
单调队列优化需要决策单调性的保证,而斜率优化不需要
斜率优化只需要能化成斜率的式子就可以了(当然如果有单调的保证可以更快一些)
------------------------------------------------
P.S. 咱语文渣请不要在意

大概就是这么一回事……
有错误的地方望神犇指正
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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