hdu 4074 Darts

时间:2021-07-23 07:44:28

思路:p[n][m][0]表示A为n,B为m,A为先手胜的概率;

         p[n][m][1]表示A为n,B为m,B为先手胜的概率。

         d[i]表示圆盘上数字的大小。

容易得到表达式为:

      hdu 4074 Darts

代码如下:

 

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define M 502
using namespace std;
double p[M][M][];
int d[]={,,,,,,,,,,,,,,,,,,,,,};
int cal(int a,int b){ return a>=b?a-b:a;}
int main()
{
int n,m;
for(n=;n<M;n++){
p[][n][]=;
p[n][][]=;
}
for(n=;n<M;n++)
for(m=;m<M;m++){
if(n<=) p[n][m][]=n/20.0;
if(m<=) p[n][m][]=m/3.0;
for(int k=;k<;k++){
double a=;
for(int i=;i<=;i++)
a+=p[cal(n,d[i])][m][];
p[n][m][]=-a/20.0;
double b=1e300;
for(int i=;i<=;i++){
double c=;
for(int j=-;j<=;j++)
c+=p[n][cal(m,d[i+j])][];
c/=3.0;
if(b>c) b=c;
}
p[n][m][]=-b;
if(n>) break;
}
}
while(scanf("%d",&n)&&n){
printf("%.12lf %.12lf\n",p[n][n][],p[n][n][]);
}
return ;
}