題目大意： 有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.2cto.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; }
