hdu 4870 Rating(高斯消元求期望) - c++编程基础

TOP

hdu 4870 Rating(高斯消元求期望)

2015-07-20 18:04:06 来源: 作者: 【大中小】浏览:2次

题意：有两个号，初始分数都是0，每次选一个分数较小的打比赛，如果分数一样任选一个，有p的概率涨50分，最高为1000分，有1-p的概率跌100分，最低为0分。问有一个号涨到1000需要打比赛的次数的期望。

令(x, y)表示高分为x，低分为y的状态（x >= y），E(x, y)表示从(x, y)到达(1000, ?)的比赛场数期望。容易得到E(x, y) = P * E(x1, y1) + (1 - P) * E(x2, y2) + 1，其中，(x1, y1)表示rating上升后的状态，（x2, y2）表示rating下降后的状态。每50分一个状态，共有210个状态。

移项后得E(x, y) -P * E(x1, y1) - (1 - P) * E(x2, y2) = 1，共有210个这样的方程组。高斯消元求解，x[0]代表E(0,0)这个状态到目标状态的期望。

注意精度。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int maxn = 231; double a[235][235],p; int equ,var; double x[235]; int flag[235][235]; int cnt; double Gauss() { int row,col,max_r; int i,j; row = col = 0; while(row < equ && col < var) { max_r = row; for(i = row+1; i < equ; i++) if(fabs(a[i][col])-fabs(a[max_r][col]) > eps) max_r = i; if(max_r != row) { for(j = col; j <= var; j++) swap(a[row][j],a[max_r][j]); } if(fabs(a[row][col]) < eps) { col++; continue; } for(i = row+1; i < equ; i++) { if(fabs(a[i][col]) > eps) { double t = a[i][col]/a[row][col]; a[i][col] = 0.0; for(j = col+1; j <= var; j++) a[i][j] -= a[row][j]*t; } } row++; col++; } for(i = equ-1; i >= 0; i--) { if(fabs(a[i][i]) < eps) continue; double tmp = a[i][var]; for(j = i+1; j < var; j++) tmp -= a[i][j]*x[j]; x[i] = tmp/a[i][i]; } return x[0]; } int main() { cnt = 0; memset(flag,-1,sizeof(flag)); for(int i = 0; i < 20; i++) { for(int j = 0; j <= i; j++) flag[i][j] = cnt++; } while(~scanf(%lf,&p)) { equ = var = 210; int x; memset(a,0,sizeof(a)); for(int i = 0; i < 20; i++) { for(int j = 0; j < i; j++) { x = flag[i][j]; a[x][x] = 1; a[x][210] = 1; a[x][flag[i][max(0,j-2)]] -= (1-p); a[x][flag[i][j+1]] -= p; } x = flag[i][i]; a[x][x] = 1; a[x][210] = 1; a[x][flag[i][max(0,i-2)]] -= (1-p); a[x][flag[i+1][i]] -= p; } printf(%.6lf , Gauss()); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 2054 Color a Tree(贪心)	下一篇：uva 548(二叉树)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: