hdu4418 Time travel 【期望dp + 高斯消元】

题目链接

题解

题意：从一个序列上某一点开始沿一个方向走，走到头返回，每次走的步长各有概率，问走到一点的期望步数，或者无解

我们先将序列倍长形成循环序列，\(n = (N - 1) \times 2\)

按期望\(dp\)的套路，我们设\(f[i]\)为从\(i\)点出发到达终点的期望步数【一定要这么做，不然转移方程很难处理】，显然终点\(f[Y] = f[(n - Y) \mod n] = 0\)

剩余的点

\[f[i] = \sum\limits_{j = 1}^{M} p_j(f[(i + j) \mod n] + j)
\]

这是一个有后效性的转移方程，高斯消元即可

但还没完，有时候有些点是无法到达的，比如每次\(100 \%\)走两步时，恰好\(n\)又是奇数

这个时候这些点无解，但不代表终点无解

我们只需\(bfs\)一遍，强行将无法到达的点设为\(INF\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

#define res register

#define eps 1e-9

using namespace std;

const int maxn = 205,maxm = 100005;

const double INF = 100000000000000000ll;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

double A[maxn][maxn],p[maxn],ans[maxn];

int n,N,M,Y,X,D,vis[maxn];

int q[maxn],head,tail;

bool bfs(){

	for (res int i = 0; i < n; i++) vis[i] = false;

	vis[X] = true; q[head = tail = 0] = X;

	int u;

	while (head <= tail){

		u = q[head++];

		for (res int i = 1; i <= M; i++)

			if (p[i] > eps){

				int to = ((u + i) % n + n) % n;

				if (!vis[to]) vis[to] = true,q[++tail] = to;

			}

	}

	for (int i = 0; i < n; i++) if (!vis[i]){

		A[i][n] = INF,A[i][i] = 1;

	}

	return vis[Y] || vis[(n - Y) % n];

}

void pre(){

	for (int i = 0; i < n; i++)

		if (vis[i]){

			A[i][i] = 1;

			if (i == Y || i == (n - Y) % n) continue;

			for (int j = 1; j <= M; j++){

				int u = ((i +  j) % n + n) % n;

				A[i][u] += -p[j];

				A[i][n] += p[j] * j;

			}

		}

}

bool gause(){

	for (res int i = 0; i < n; i++){

		int j = i;

		for (res int k = i + 1; k < n; k++)

			if (fabs(A[k][i]) > fabs(A[j][i])) j = k;

		if (j != i) for (int k = i; k <= n; k++) swap(A[i][k],A[j][k]);

		if (fabs(A[i][i]) < eps) return false;

		for (res int j = i + 1; j < n; j++){

			double t = A[j][i] / A[i][i];

			for (res int k = i; k <= n; k++)

				A[j][k] -= A[i][k] * t;

		}

	}

	for (res int i = n - 1; ~i; i--){

		for (res int j = i + 1; j < n; j++)

			A[i][n] -= A[i][j] * ans[j];

		if (fabs(A[i][i]) < eps) return false;

		ans[i] = A[i][n] / A[i][i];

	}

	return true;

}

int main(){

	int T = read();

	while (T--){

		N = read(); M = read(); Y = read(); X = read(); D = read();

		n = 2 * (N - 1);

		if (D == -1){

			if (X == 0) D = 0;

			else D = 1;

		}

		if (D >= 1) X = (n - X) % n;

		for (int i = 1; i <= M; i++)

			p[i] = read() / 100.0;

		if (X == Y){puts("0.00"); continue;}

		for (res int i = 0; i < n; i++)

			for (res int j = 0; j <= n; j++)

				A[i][j] = 0;

		if (!bfs()) {puts("Impossible !"); continue;}

		pre();

		if (!gause() || ans[X] >= INF)

			puts("Impossible !");

		else printf("%.2lf\n",ans[X]);

	}

	return 0;

}

巴特西

hdu4418 Time travel 【期望dp + 高斯消元】

题目链接

题解

最新文章

热门文章