CF 150C Smart Cheater
题目大意：
有n个站台，编号1~n，第i站台的坐标为xi （0 = x0 < x1 < x2...）。
a站台到b站点的花费为xb-xa.
m个人坐车，第i个人在第ai站上车，bi站下车（1 <= ai < bi <=n）。
售票员卖票时最多可以从[a,b]中选一段[c,d]（c <= d）不计入票价，这一部分的钱售票员和乘客一人一半。
由于司机可能在[xi,xi+1]有pi的可能性查票，如果查到有人没买这段的票就要罚售票员c钱。
问售票员的最大期望收益。
题目思路：
每个人是独立的，且[xi,xi+1]和[xi+1,xi+2]之间也是独立的。
所以单独考虑每个人对于售票员的最大期望收益，加起来就是总的最大期望收益。
设某一个乘客的a上b下，即[a,b]。
把[a,b]看为[a,a+1],[a+1,a+1],...,[b-1,b]，a-b个点，而每个点都有一个权值，权值为其期望值。
则该乘客对于售票员的最大期望就是[a,b]的期望值的最大连续子段和。
到了这一步，很容易可以想到这是一道裸的区间并的线段树。
代码：
[cpp]
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-8)
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#define _mod(x,y) ((x)>0? (x)%(y):((x)%(y)+(y))%(y))
#define _abs(x) ((x)<0? (-(x)):(x))
#define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x))
#define getmax(x,y) (x= ((y)>(x))? (y):(x))
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
int TS,cas=1;
const int M=150000+5;
int n,m;
ll x[M],p[M],c;
double val[M];
struct node{
double lmax,rmax,mmax,sum;
void init(int i){
lmax=rmax=mmax=sum=val[i];
}
}nd[M<<2];
void func(node& l,node& r,node& rt){
rt.sum=l.sum+r.sum;
rt.lmax=_max(l.lmax,l.sum+r.lmax);
rt.rmax=_max(r.rmax,r.sum+l.rmax);
rt.mmax=_max(_max(l.mmax,r.mmax),l.rmax+r.lmax);
}
void pushUp(int rt){
func(nd[ls],nd[rs],nd[rt]);
}
void build(int l,int r,int rt){
if(l==r){
nd[rt].init(l);
return;
}
int mid=middle;
build(lson),build(rson);
pushUp(rt);
}
node query(int l,int r,int rt,int L,int R){
if(L<=l && r<=R){
return nd[rt];
}
int mid=middle;
if(R<=mid) return query(lson,L,R);
if(mid<L) return query(rson,L,R);
node lr=query(lson,L,mid);
node rr=query(rson,mid+1,R);
node res;
func(lr,rr,res);
return res;
}
void run(){
int i,j;
for(i=1;i<=n;i++)
scanf("%I64d",&x[i]);
n--;
for(i=1;i<=n;i++)
scanf("%I64d",&p[i]);
for(i=1;i<=n;i++)
val[i]=1.0*p[i]/100.0*(1.0*(x[i+1]-x[i])/2.0-1.0*c)+(1.0-1.0*p[i]/100.0)*(1.0*(x[i+1]-x[i])/2.0);
build(1,n,1);
int a,b;
double ret=0;
while(m--){
scanf("%d%d",&a,&b);
double tmp=query(1,n,1,a,b-1).mmax;
if(tmp > 0) ret+=tmp;
}
printf("%.9lf\n",ret);
} www.zzzyk.com
void preSof(){
}
int main(){
//freopen("inputxt","r",stdin);
//freopen("outputxt","w",stdout);
preSof();
//run();
while(~scanf("%d%d%I64d",&n,&m,&c)) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}
补充：软件开发 , C++ ,
