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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1568][JSOI2008]Blue Mary开公司  

2015-01-02 14:47:42|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1568: [JSOI2008]Blue Mary开公司

去年pz大爷发的测试题里的一道……
拖到现在才过……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
const double eps = 1e-9;
int n,m,tmp[N],ke[N],pn;
double pk[N],ans[N];
int ask[N][2];
struct Point{Point(double a=0,double b=0):x(a),y(b){}double x,y;}data[N];
Point operator-(const Point&a,const Point&b){return Point(a.x-b.x,a.y-b.y);}
double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
double calck(Point a,Point b){return 1.*(b.y-a.y)/(b.x-a.x);}
double calcm(Point a,double k){return -k*a.x + a.y;}
bool better(Point a,Point b,Point c){return Cross(a-b,b-c)>=0;}
bool dcmp(double a,double b){return fabs(a-b)<=eps;}
bool pcmp(int A,int B){
Point &a=data[A],&b=data[B];
return dcmp(a.x,b.x)?a.y>b.y:a.x<b.x;
}
bool cmpk(double a,double b){return a>b;}
deque<int>dui;
int solve(int l=1,int r=n){
if(l==r){
if(ask[l][0] == 0)return 0;
ke[l]=ask[l][1];
pk[l]=1e50;
return 1;
}
int mid = (l+r)/2,len[2],i,j,re=0;
len[0] = solve(l,mid);len[1] = solve(mid+1,r);
for(i=mid+1;i<=r;i++)
if(ask[i][0]==0){
j = lower_bound(pk+l,pk+l+len[0],1-ask[i][1],cmpk)-pk-1;
double atmp=calcm(data[ke[j]],1-ask[i][1]);
if(atmp > ans[i])ans[i] = atmp;
}
//merge
merge(ke+l,ke+l+len[0],ke+(mid+1),ke+(mid+1)+len[1],tmp+1,pcmp);
for(i=1;i<=len[0]+len[1];i++)
if(i==1||dcmp(data[tmp[i]].x,data[tmp[i-1]].x)==0){
int now = tmp[i];
while((j=dui.size())>1 && better(data[dui[j-2]],data[dui[j-1]],data[now]))dui.pop_back();
dui.push_back(now);
}
while(!dui.empty()){
int p = (++re)+l-1;
ke[p] = dui.front();dui.pop_front();
if(re-1>=1)pk[p] = calck(data[ke[p-1]],data[ke[p]]);
else pk[p] = 1e50;
}
return re;
}
int main(){
int i,j,a;char opt[20];
double fa,fb;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s",opt+1);
switch(opt[1]){
case'Q':
scanf("%d",&a);
ask[i][0] = 0;ask[i][1] = a;
break;
case'P':
scanf("%lf%lf",&fa,&fb);
data[++pn] = Point(fb,fa);
ask[i][0] = 1;ask[i][1] = pn;
break;
}
}
solve();
for(i=1;i<=n;i++)
if(ask[i][0]==0){
printf("%d\n",(int)((ans[i]+eps)/100));
}
return 0;
}

题解:
分治/维护动态凸壳。
设第i个顾问开始收益为si,每天增加量是di 
那么第j天的收益就是z = si+(j-1)*di 
设si = y,di = x 
z = y+(j-1)*x 
y = (1-j)x + z 
si = (1-j)di + z
  要最大化z,常见模型,维护一个上凸壳就行了
直接splay搞或者离线之后分治都行,因为splay太难写而且没有强制在线所以就直接分治了。。
  评论这张
 
阅读(38)| 评论(10)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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