| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:原来是个神题,大拜神犇……In Reply To:原来是个水题,大失所望…… Posted by:applepi at 2011-05-30 15:06:27 带环概率DP各种尼玛啊……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double f[34][34][2],pt3,pt2,def,reb,opt3,opt2,odef,oreb,ans;
int n,m,i,j;
double calc(double pt3,double pt2,double def,double reb)
{
double t3,g3,g2,r,ot3,og3,og2,ore,p1,p2,p3,p4,op1,op2,op3,op4,k1,k2,k4,ok1,ok2,ok4,a,b,c,d;
t3=pt3/(pt2+pt3);
g3=0.8*pt3/(pt3+odef);
g2=pt2/(pt2+odef);
r=0.8*reb/(reb+oreb);
ot3=opt3/(opt2+opt3);
og3=0.8*opt3/(opt3+def);
og2=opt2/(opt2+def);
ore=0.8*oreb/(oreb+reb);
p1=t3*g3;
p2=(1-t3)*g2;
p3=r*(1-p1-p2);
p4=(1-r)*(1-p1-p2);
op1=ot3*og3;
op2=(1-ot3)*og2;
op3=ore*(1-op1-op2);
op4=(1-ore)*(1-op1-op2);
k1=p1/(1-p3);
k2=p2/(1-p3);
k4=p4/(1-p3);
ok1=op1/(1-op3);
ok2=op2/(1-op3);
ok4=op4/(1-op3);
for(i=n;i<34;i++)
for(j=0;j<n;j++)
{
f[i][j][0]=f[i][j][1]=1;
f[j][i][0]=f[j][i][1]=0;
}
for(i=n-1;i>=0;i--)
for(j=n-1;j>=0;j--)
{
a=k4,c=ok4;
b=k1*f[i+3][j][0]+k2*f[i+2][j][0];
d=ok1*f[i][j+3][1]+ok2*f[i][j+2][1];
f[i][j][0]=(b+a*d)/(1-a*c);
f[i][j][1]=(b*c+d)/(1-a*c);
}
return f[0][0][0];
}
int main ()
{
while(cin>>n>>m>>opt2>>opt3>>oreb>>odef)
{
ans=0;
for(pt3=1;pt3<=10;pt3++)
{
if(m-pt3<3) break; if(m-pt3>30) continue;
for(pt2=1;pt2<=10;pt2++)
{
if(m-pt3-pt2<2) break; if(m-pt3-pt2>20) continue;
for(def=1;def<=10;def++)
{
reb=m-pt3-pt2-def;
if(reb<1) break; if(reb>10) continue;
ans=max(ans,calc(pt3,pt2,def,reb));
}
}
}
printf("%.3f\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator