hdu 4870 Rating

제목은 간단하다. 이산화한 다음에 dp방정식 E[i][j]=E[i][j-2]*(1-p)+E[i][j+1]*p+1;(i>=j로 가정)
E[i][j-2]가 계산하지 못한 문제가 존재하기 때문에 dp가 해결할 수 없기 때문에 고스 소원을 고려합니다.
방정식 변형 E[i][j]-(1-p)*E[i][j-2]-p*E[i][j+1]=1;
그리고 모든 상태는 대응하는 방정식이 있고 각 방정식은 하나의 표현식이 있으며 고스 소원으로 이 표현식을 풀 수 있다.결국 x[0]의 해!

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define B(x) (1<<(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
void cmax(int& a, int b){ if (b>a)a = b; }
void cmin(int& a, int b){ if (b<a)a = b; }
void cmax(ll& a, ll b){ if (b>a)a = b; }
void cmin(ll& a, ll b){ if (b<a)a = b; }
void add(int& a, int b, int mod){ a = (a + b) % mod; }
void add(ll& a, ll b, ll mod){ a = (a + b) % mod; }
const int oo = 0x3f3f3f3f;
const ll OO = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1000000007;
const int maxn = 300;
const double eps = 1e-6;
double a[maxn][maxn];
int id[maxn][maxn], cnt;
double p;

void Init(){
	for (int i = 0; i < maxn; i++)
	for (int j = 0; j < maxn; j++)
		a[i][j] = 0.0;
}

void build(int n){
	cnt = 0;
	memset(id, -1, sizeof id);
	for (int i = 0; i < n; i++){
		for (int j = 0; j <= i; j++)
			id[i][j] = cnt++;
	}
	Init();
	int nx, ny, u, v;
	for (int i = 0; i < n; i++){
		for (int j = 0; j <= i; j++){
			u = id[i][j];
			a[u][u] = 1.0;
			a[u][cnt] = 1.0;
			nx = max(i, j + 1), ny = min(i, j + 1);
			v = id[nx][ny];
			a[u][v] -= p;
			nx = i, ny = max(0, j - 2);
			v = id[nx][ny];
			a[u][v] -= (1 - p);
		}
	}
}

double Gauss(int n, int m){
	int r, c;
	for (r = 0, c = 0; r < n && c < m; r++, c++){
		int k = r;
		for (; k < n; k++)
			if (fabs(a[k][c]) > eps) 
				break;
		if (fabs(a[k][c]) < eps) continue;
		if (k != r){
			for (int j = 0; j <= m; j++)
				swap(a[k][j], a[r][j]);
		}
		for (int i = 0; i < n; i++){
			if (i == r) continue;
			if (fabs(a[i][c]) < eps) continue;
			double t = a[i][c] / a[r][c];
			for (int j = c; j <= m; j++)
				a[i][j] -= a[r][j] * t;
		}
	}
	return a[0][m] / a[0][0];
}

int main(){
	//freopen("E:\\read.txt","r",stdin);
	while (scanf("%lf", &p) != EOF){
		build(20);
		printf("%.6lf
", Gauss(cnt, cnt));
	}
	return 0;
}