题意 一个人打比赛 ,rating 有p的概率 为加50分 有1-p的概率为 x-100分 最大值为 1000 最小值为0
有两个号 每次拿较小的号来提交 , 计算最后到达 1000分得期望场数是多少,
对每个状态建立一个方程然后用高斯消元解决
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=;
const double eps=0.000000001;
int sgn(double f){
if(fabs(f)<eps)return ;
return f>?:-;
}
int id[maxn][maxn],cnt;
int equ,var;//方程数和未知数个数
double P;
double a[][],x[];
void perId()
{
cnt=;
for(int i=; i<; i++)
for(int j=; j<=i; j++)
id[i][j]=cnt++;
id[][]=cnt++;
equ=var=cnt;
}
void init()
{
memset(a,,sizeof(a));
for(int i=; i<; i++)
for(int j=; j<=i ;j ++)
{
int u=id[i][j];
x[ u ]=a[ u ][ u ] = 1.0;
int nx,ny;
nx=max( i , j+ ),ny=min( i , j+ );
a[ u ][ id[nx][ny] ]-=P;
nx=i; ny=max(j-,);
a[ u ][ id[nx][ny] ]-=(-P);
}
x[cnt-]=0.0;
a[cnt-][cnt-]=1.0;
} int Gauss()
{
int i,j,k,col,max_r;
for(k=,col=;k<equ&&col<var;k++,col++)
{
max_r=k;
for(i=k+;i<equ;i++)
if(fabs(a[i][col])>fabs(a[max_r][col]))
max_r=i;
if(k!=max_r)
{
for(j=col;j<var;j++)
swap(a[k][j],a[max_r][j]);
swap(x[k],x[max_r]);
}
x[k]/=a[k][col];
for(j=col+;j<var;j++)a[k][j]/=a[k][col];
a[k][col]=;
for(i=;i<equ;i++)
if(i!=k)
{
x[i]-=x[k]*a[i][col];
for(j=col+;j<var;j++)a[i][j]-=a[k][j]*a[i][col];
a[i][col]=;
}
}
return ;
}
int main()
{
perId(); while(scanf("%lf",&P)==)
{
init();
Gauss();
printf("%.6lf\n",x[]);
}
return ;
}