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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3437]小P的牧场  

2015-06-17 21:52:46|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3437: 小P的牧场

好久没更blog了……本来都打算一直坑着
结果是最近看了别的神犇的题解后突然燃起了blog之魂(?
补几篇最近的题解吧……反正也马上放学了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1E6+100;
int n,m,ai[N],bi[N];
ll sum[N],f[N],sum2[N];
int dui[N],dl,dr,from[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;
}
//inline ll calc(int j,int i){ return f[j] + (sum[i]-sum[j])*(i-j) + ai[i];}
ll calc(int j,int i){
return f[j] + (sum[i]-sum[j])*i - (sum2[i]-sum2[j]) + ai[i];
}
int main(){
// freopen("in.txt","r",stdin);
int i,j;
n = scan();
for(i=1;i<=n;i++)
ai[i] = scan();
for(i=1;i<=n;i++){
bi[i] = scan();
sum[i] = sum[i-1] + bi[i];
sum2[i] = sum2[i-1] + (ll)i*bi[i];
}
dl = dr = 1;
dui[1] = 1;from[1] = 0;
for(i=1;i<=n;i++){
//update f
dui[dl] = i+1;
if(dl < dr && dui[dl+1] <= i)dl++;
f[i] = calc(from[dl],i);
// printf("%d ",f[i]);
if(i == n)break;
//update jc
int last = n+1;
while(dl <= dr && calc(i,dui[dr]) < calc(from[dr],dui[dr])){
last = dui[dr];
dr--;
}
if(dl <= dr){
int l,r;
l = dui[dr]+1;r = last;
while(l < r){
int mid = (l+r)/2;
if(calc(i,mid) <= calc(from[dr],mid))r = mid;
else l = mid+1;
}
if(l <= n){
dui[++dr] = l;
from[dr] = i;
}
}else{
dui[++dr] = i+1;
from[dr] = i;
}
}
printf("%lld\n",f[n]);
return 0;
}

题解:
一开始读错题了……搞了个式子出来,觉得这玩意好眼熟啊
想了一会儿发现是一轮集训的时候的一道傻逼决策单调性
当时想了好久不会做……结果讲题的时候才想起来还有这么个算法
写暴力看了看决策单调,写完程序又拍了一下觉得没问题就交了……结果0ms WrongAnswer
然后发现样例都过不了……
又读了一下题
设sum=Σbi sum2=Σi*bi
然后式子是
f[i] = max {f[j] + (sum[i]-sum[j])*i - (sum2[i]-sum2[j]) + a[i]}
f[i] = max {f[j] + (sum[i]-sum[j])*i} - (sum2[i]-sum2[j]) + a[i]
感觉比原来那个式子漂亮,好像可以斜率优化……
x = sum[j]  y = f[j]+sum2[j] k=i
最小化Z: Z = y - k*x
k*x + Z = y
Z是截距
显然由高中线性规划知识得最优值在下凸壳上
因为k单调所以决策单调
因为x单调所以凸包随便建
可以斜率优化了

人懒没写代码
  评论这张
 
阅读(51)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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