鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4870

題意：用兩個(gè)賬號去參加一種比賽，初始狀態(tài)下兩個(gè)賬號都是零分，每次比賽都用分?jǐn)?shù)低的賬號去比賽。有P的概率取勝，相應(yīng)賬號分?jǐn)?shù)上漲50分，否則相應(yīng)賬號分?jǐn)?shù)下降100分，問當(dāng)有一個(gè)賬號分?jǐn)?shù)達(dá)到1000分時(shí)參加比賽次數(shù)的數(shù)學(xué)期望是多少。

思路：比賽期間以為是一道推公式的題，推了半天沒什么收獲。

賽后想了想。看了解題報(bào)告以后。知道了這樣的每一個(gè)分?jǐn)?shù)相應(yīng)狀態(tài)受到兩個(gè)狀態(tài)以上推得而且不是從后向前推得情況能夠用高斯消元來解。狀態(tài)0~狀態(tài)209分別代表者分?jǐn)?shù)為(0,0),(50,0)...(950,950)到有一個(gè)賬號的分?jǐn)?shù)為1000的數(shù)學(xué)期望。E(X,Y)=p(E(x1,y1)+1)+(1-p)(E(x2,y2)+1)，(x1,y1)代表著這次比賽取勝之后兩個(gè)賬號的分?jǐn)?shù)，(x2,y2)代表著這次比賽失敗之后兩個(gè)賬號的分?jǐn)?shù)。

狀態(tài)中不用計(jì)入狀態(tài)(1000,?)是由于除了(1000,950)外其它狀態(tài)不會出現(xiàn)。而(1000,950)狀態(tài)僅僅與狀態(tài)(950,950)有關(guān)，而且(950,950)不會從(1000,950)得到，210個(gè)狀態(tài)中沒有狀態(tài)是與(1000,?

)狀態(tài)相關(guān)，所以不須要處理。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <cstdlib> #include <queue> #include <stack> #include <vector> #include <ctype.h> #include <algorithm> #include <string> #include <set> #define PI acos(-1.0) #define maxn 210 #define INF 0x7fffffff #define eps 1e-8 #define MOD 1000000009 typedef long long LL; typedef unsigned long long ULL; using namespace std; double a[220][220],b[220]; int all[25]; double gauss_elimination(int n) {int i,j,k,row;double maxp,t;for(k=0; k<n; k++){for(maxp=0,i=k; i<n; i++)if (fabs(a[i][k])>eps){maxp=a[row=i][k];break;}if(fabs(maxp)<eps) return 0;if(row!=k){for(j=k; j<n; j++)swap(a[k][j],a[row][j]);swap(b[k],b[row]);}for (int j = 0; j < n; j++){if (k == j) continue;if (fabs(a[j][k]) > eps){double x = a[j][k] / a[k][k];for (int i = k; i < n; i++){a[j][i] -= a[k][i] * x;}b[j] -=b[k]*x;}}}return 1; } int init() {all[0]=0;for(int i=1; i<=21; i++){all[i]=all[i-1]+i;}return 0; } int main() {double p;init();while(~scanf("%lf",&p)){memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=0; i<20; i++){for(int j=0; j<=i; j++){a[all[i]+j][all[i]+j]+=1;b[all[i]+j]+=1;a[all[i]+j][all[i]+max(j-2,0)]+=(p-1);if(j+1<=i)a[all[i]+j][all[i]+j+1]+=(-p);else{if(i==19&&j==19)continue;else a[all[i]+j][all[j+1]+i]+=(-p);}}}gauss_elimination(210);printf("%.6lf\n",b[0]/a[0][0]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/gcczhongduan/p/5059758.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4870 Rating 高斯消元法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。