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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3156]防御准备  

2014-10-29 21:58:52|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

还算是比较裸的题

写了两个版本的代码


Version 1.0 : 决策单调性:单调队列 NlogN 

/*

for i we have
j < k
jc[j] >= jc[k]

when i+? also right

f[j] + Sn[i-j-1] >= f[k] + Sn[i-k-1]

f[j] + (i-j)*(i-j-1)/2 >= f[k] + (i-k)*(i-k-1)/2

f[j]*2 + (i-j)*(i-j-1) >= f[k]*2 + (i-k)*(i-k-1)

f[j]*2 - f[k]*2 >= (i-k)*(i-k-1) - (i-j)*(i-j-1)

f[j]*2 - f[k]*2 >= (i-k)^2 - (i-k) - ((i-j)^2 - (i-j))

f[j]*2 - f[k]*2 >= (i-k)^2 - (i-j)^2 + (i-j) - (i-k)

f[j]*2 - f[k]*2 >= -2*k + k*k + 2*j -j*j + k-j

f[j]*2 - f[k]*2 >= (k+j)*(k-j) + (j-k)

f[j] - f[k] >= (k+j-1)*(k-j)/2;

决策单调性证毕
*/

/*
Version 1.0
单调栈NlogN
*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
typedef long long LL;
const int N = 1E6+120;
const LL MAX = 1e18+10;
int n,m,data[N],last[N];
LL f[N];
int scan(){int i=0;scanf("%d",&i);return i;}
LL Sn[N];
//bool better(int j,int k){return f[j] - f[k] >= (k+j-1)*(k-j)/2;}
typedef pair<int,int> Data;
bool better(Data a,int now){return f[now]+Sn[a.second-now-1] <= f[a.first]+Sn[a.second-a.first-1] ;}
deque<Data>dui;
int main(){
int i,j;
freopen("in.txt","r",stdin);
n = scan();
for(i=1;i<=n;i++)data[n-i+1] = scan(),f[i] = MAX;
f[0] = data[++n] = 0;
f[n] = MAX;
LL tmp;
for(i=1;i<=n;i++)Sn[i] = Sn[i-1] + i;
f[1] = data[1];
dui.push_back(Data(1,2));

int now,d;
for(i=2;i<=n;i++){
//update f[i]
//while(dui.size() > 1 && dui[1].second <= i)dui.pop_front();
now = dui[0].first;
last[i] = now;
f[i] = f[now] + Sn[i-now-1] + data[i];
//update dui
int l,r=n+1;
while((d=dui.size())>0 && better(dui[d-1],i))
r=dui.back().second,dui.pop_back();
if(dui.empty()){dui.push_back(Data(i,i+1));continue;}
now = dui.back().first;
l = dui.back().second+1;
l = max(l,i+1);
while(l<r){
int mid = (l+r)/2;
if(f[i]+Sn[mid-i-1] <= f[now]+Sn[mid-now-1])r = mid;
else l = mid+1;
}
if(l!=n+1)dui.push_back(Data(i,l));
if(dui.size() > 1 && dui[1].second == i+1)dui.pop_front();
}
printf("%lld",f[n]);
return 0;
}



Version 2.0 斜率优化 N

/*


f[i] = min((i-j-1) * (i-j)/2 + f[j]) + data[i]

f[i] = min((i-1)* (i-j)/2 -j * (i-j)/2 + f[j]) + data[i]

f[i] = min(j -2*i*j+j*j + f[j]*2)/2 + (i*i-i)/2 + data[i]

f[i] = min( (f[j]*2+ j*j+j)/2 - i*j ) + (i*i-i)/2 + data[i]

y = f[j]*2+j*j+j
x = j
*/

/*
Version 2.0
斜率优化
*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 1E6+120;
const LL MAX = 1e18+10;
int n,m,data[N],last[N];
LL f[N];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'|| cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
LL getx(LL i){return i;}
LL gety(LL i){return (f[i]*2+i*i+i)/2;}
typedef pair<LL,LL> Data;
deque<Data>dui;
bool better(Data a,Data b,LL i){return (a.second - i*a.first) >= (b.second - i*b.first);}
double getk(Data a,Data b){return (double)(b.second - a.second)/(b.first - a.first);}
const double eps = 1e-9;
bool needpop(Data a,Data b,Data c){return getk(a,b) - getk(a,c) > eps;}
int main(){
int i,j;
//freopen("in.txt","r",stdin);
n = scan();
for(i=1;i<=n;i++)data[n-i+1] = scan(),f[i] = MAX;
f[0] = data[++n] = 0;
f[n] = MAX;
f[1] = data[1];
dui.push_back(Data(getx(1),gety(1)));
LL now;
for(i=2;i<=n;i++){
while(dui.size() > 1 && better(dui[0],dui[1],i))dui.pop_front();
now = dui[0].first;
f[i] = (dui[0].second - now*i) + ((LL)i*i-i)/2 + data[i];
Data Dnow = Data(getx(i),gety(i));
while((j=dui.size()) > 1 && needpop(dui[j-2],dui[j-1],Dnow))dui.pop_back();
dui.push_back(Dnow);
}
printf("%lld",f[n]);
return 0;
}

题解:

很明显是DP

把数组左右翻转一下,f[i]表示最后一个塔在i位置所需要的最小消费

f[1] = data[1] (i=1)

= min(f[j] + (i-j)*(i-j-1)/2)+data[i] (i>1)

使得在n+1位置放塔的花费是0,那么答案就是f[n+1]

然后可以证得(证明在代码Ver1.0里)假如对于位置i有两个决策j,k(j < k)满足k比j优,那么对于位置大于i的位置也满足这个。

所以得到决策单调

得到NlogN的做法1:没得到一个f[i]就将其作为决策更新后面的f,要用二分找合适的位置


然后zky神犇下午说他用斜率优化A了这道题……

我表示不信。。连斜率的形式都没有怎么搞?

然后他列出了式子:

f[i]=a[i]+(i*i-i)/2+min(f[j]+(j*j+j)/2-ij)

也就是把只和i有关的提了出来。

令Y = f[j]+(j*j+j)/2 X = j

维护一个下凸壳每次在上面三分找最优解。

那么问题来了:

我:“为啥答案一定在下凸壳上?”

Zky:"……不知道,结论。"

Wangxz:“线性规划啊”

我&zky:Orz!!

令z = y - k*x (k = i)

最小化z,相当于使得y = z + k*x这个直线的纵截距最小

然后由数学老师课上讲的线性规划姿势可得最优解一定是在下凸壳上(稍微有点区别因为这里的可行域是点集)

但是似乎有些更好的性质?

注意到X = j是个单调递增的,并且我们查询的斜率k=i也是单调递增的!

所以用优先队列可以O(n)解决。


不过这样一来,似乎之前我做的斜率优化题目都可以用决策单调性做?

果然这个地方还是有点晕+_+

  评论这张
 
阅读(224)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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