首页 > 代码库 > BZOJ3795 : 魏总刷DP
BZOJ3795 : 魏总刷DP
对于HARD：
需要满足$k+u[i]\times k\leq T+late[i]$。
对于EASY：
需要满足$k+u[i]\times k\leq T-rest[i]$。
故对于HARD，设$a[i]=-late[i]$，对于EASY，设$a[i]=rest[i]$，并将所有题目的$u[i]$都$+1$。
那么需要满足$\max(u[i]\times k+a[i])\leq T$。
求出这些直线形成的下凸壳，分段积分即可。
时间复杂度$O(n\log n)$。
#include<cstdio>#include<algorithm>using namespace std;const int N=100010;const double eps=1e-9;int n,i,x,q[N],t;char ch[9];double m,L,R,f[N],ans;struct P{int k,b;}a[N];inline bool cmp(const P&a,const P&b){return a.k==b.k?a.b>b.b:a.k<b.k;}inline double pos(int x,int y){return 1.0*(a[x].b-a[y].b)/(a[y].k-a[x].k);}inline int sgn(double x){ if(x>eps)return 1; if(x<-eps)return -1; return 0;}inline void cal(double l,double r,int k,int b){ l=max(l,0.0),r=min(r,min(m,(R-b)/k)); if(l+eps>r)return; double mid=min(max((L-b)/k,l),r); ans+=(mid-l)*(R-L)+(R-b)*(r-mid)-(r*r-mid*mid)*k/2;}int main(){ scanf("%d%lf%lf%lf",&n,&m,&L,&R); for(i=1;i<=n;i++)scanf("%d",&a[i].k),a[i].k++; for(i=1;i<=n;i++){ scanf("%s%d",ch,&x); if(ch[0]==‘H‘)a[i].b=-x;else a[i].b=x; } sort(a+1,a+n+1,cmp); for(q[t=1]=1,i=2;i<=n;i++)if(a[i].k>a[i-1].k){ while(t>1&&sgn(pos(q[t-1],q[t])-pos(q[t],i))>=0)t--; q[++t]=i; } for(f[t]=m,i=1;i<t;i++)f[i]=pos(q[i],q[i+1]); for(i=1;i<=t;i++)cal(f[i-1],f[i],a[q[i]].k,a[q[i]].b); return printf("%.4f",ans/m/(R-L)),0;}
BZOJ3795 : 魏总刷DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。