HDU 4870 Rating（高斯消元)

HDU 4870 Rating

題目鏈接

題意：一個人注冊兩個賬號，初始rating都是0，他每次拿低分的那個號去打比賽，贏了加50分，輸了扣100分，勝率為p，他會打到直到一個號有1000分為止，問比賽場次的期望

思路：f(i, j)表示i >= j，第一個號i分，第二個號j分時候，達到目標的期望，那麼可以列出轉移為f(i, j) = p f(i', j') + (1 - p) f(i'' + j'') + 1
f(i', j')對應的是贏了加分的狀態，f(i'', j'')對應輸的扣分的狀態，可以把50分當作一個單位，一共有20 * 21 / 2 = 210個狀態，也就是對應了210個方程組，利用高斯消元去求解方程組，解出f(0, 0)就是答案

代碼：

#include 
#include 
#include 
#include 
using namespace std;

const double eps = 1e-9;
const int N = 305;

double p, a[N][N];
int mark[25][25];

double solve() {
    for (int i = 0; i < 210; i ++) {
	int k = i;
	for (; k < 210; k++)
	    if (fabs(a[k][i]) > eps) break;
	for (int j = 0; j <= 210; j++)
	    swap(a[i][j], a[k][j]);
	for (int j = 0; j < 210; j++) {
	    if (i == j) continue;
	    if (fabs(a[j][i]) > eps) {
		double x = a[j][i] / a[i][i];
		for (int k = i; k <= 210; k++) {
		    a[j][k] -= a[i][k] * x;
		}
	    }
	}
    }
    return a[0][210] / a[0][0];
}

void build() {
    memset(a, 0, sizeof(a));
    for (int i = 0; i < 20; i++) {
	for (int j = 0; j < i; j++) {
	    int u = mark[i][j];
	    a[u][u] = 1;
	    a[u][210] = 1;
	    int v = mark[i][max(0, j - 2)];
	    a[u][v] -= (1 - p);
	    v = mark[i][j + 1];
	    a[u][v] -= p;
	}
	int u = mark[i][i];
	a[u][u] = 1;
	a[u][210] = 1;
	int v = mark[i][max(0, i - 2)];
	a[u][v] -= (1 - p);
	v = mark[i + 1][i];
	a[u][v] -= p;
    }
}

int main() {
    int cnt = 0;
    memset(mark, -1, sizeof(mark));
    for (int i = 0; i < 20; i++) {
	for (int j = 0; j <= i; j++) {
	    mark[i][j] = cnt;
	    cnt++;
	}
    }
    while (~scanf("%lf", &p)) {
	build();
	printf("%.6lf\n", solve());
    }
    return 0;
}