Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:原来是个神题,大拜神犇……

Posted by lydliyudong at 2012-07-02 16:54:42 on Problem 2238 and last updated at 2012-07-02 16:55:59
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator