首页 > 代码库 > bzoj 3795: 魏总刷DP
bzoj 3795: 魏总刷DP
Description
魏总，也就是DP魏又开始刷DP了。一共有n道题，第i道题魏总原本需要u[i]秒的时间。不过，为了表达对这些水题的藐视，魏总决定先睡k秒再开始刷题。魏总并不清楚自己会睡多久，只知道k是不超过m的正实数。并且魏总还忘了这节课有多长，只记得这节课的长度T（单位：秒）是在L到R之间。（魏总是从开始上课的时候开始睡的）睡醒后，魏总神奇地发现自己做每道题所需的时间变成了原来的k倍。不过DP魏就是DP魏，他可以同时做这n道DP，互不影响。
魏总本想虐场，但他很快发现自己低估这些题了。于是他决定将题分为HARD和EASY。对于每道HARD的题，他希望能最晚在下课后late[i]秒内完成，而对于EASY的题，他希望在下课前rest[i]秒之前完成。
求魏总达到目标的概率。
Input
第一行，一个整数n
第二行，三个实数m，L，R
第三行，n个整数，第i个为u[i]
就下来n行，每行一个字符串和一个整数，字符串为”HARD”或”EASY”，整数为对应的late[i]或rest[i]。
Output
一行，魏总达到目标的概率，保留4位小数。
将(k,T)看作平面上的点，约束条件为线性不等式，可以转为求半平面交的面积
#include<cstdio>#include<algorithm>const int N=100007;int n,lp=0,p=0,as[N];double xm,ym,S,S1=0,L,R;char s[16];struct pos{double x,y;}ps[N];struct ln{ double k,b; double x(double y){return (y-b)/k;} double y(double x){return k*x+b;} bool operator<(ln w)const{return k!=w.k?k<w.k:b>w.b;} bool in(pos w){return y(w.x)<=w.y;} pos operator&(ln w){ double x=(w.b-b)/(k-w.k); return (pos){x,y(x)}; }}ls[N];int main(){ scanf("%d%lf%lf%lf",&n,&xm,&L,&R); ym=R-L; S=xm*ym; for(int i=1;i<=n;++i)scanf("%d",as+i); ls[lp++]=(ln){0,0}; for(int i=1,b;i<=n;++i){ scanf("%s%d",s,&b); if(s[0]==‘E‘)b*=-1; ls[lp++]=(ln){as[i]+1,-L-b}; } std::sort(ls,ls+lp); for(int i=0;i<lp;++i){ if(i&&ls[i].k==ls[i-1].k)continue; while(p>=2&&!ls[i].in(ls[p-2]&ls[p-1]))--p; ls[p++]=ls[i]; } while(p>=2&&(ls[p-2]&ls[p-1]).x>xm)--p; int p0=0; while(p-p0>=2&&(ls[p0]&ls[p0+1]).x<0)++p0; ps[p0]=(pos){0,ls[p0].y(0)}; if(ps[p0].y>=ym)return puts("0.0000"),0; for(int i=p0+1;i<p;++i)ps[i]=ls[i]&ls[i-1]; ps[p]=(pos){xm,ls[p-1].y(xm)}; if(ps[p].y>ym){ while(p-p0>=2&&(ls[p-2]&ls[p-1]).y>ym)--p; ps[p]=(pos){ls[p-1].x(ym),ym}; } for(int i=p0+1;i<=p;++i){ S1+=(ps[i].x-ps[i-1].x)*(ym*2-ps[i].y-ps[i-1].y); } printf("%.4f",S1/S/2); return 0;}
bzoj 3795: 魏总刷DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。