meaning of the title
Copied from https://www.cnblogs.com/Paul-Guderian/p/7624039.html
Playing flying chess. Input n,m means that the flying chess has n squares and m flying points, then input m to u,v means that u point can fly directly to v point, i.e. u is the flying point. If the grid is not a flight point, throw dice (1-6 equal probability) to move forward. Otherwise, fly directly to the target point. Each grid is the only starting point, but not the only ending point. Ask the expected number of dice that arrive or cross the finish line.
Start from 0!!
Sol
Comparing the expectation dp of zz
Let $f[i] $indicate the expected steps from $I $to $n $
Just discuss it when transferring
/* */ #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<set> #include<queue> #include<cmath> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) #define fi first #define se second //#define int long long //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 22)], *p1 = buf, *p2 = buf; using namespace std; const int MAXN = 1e5 + 10, INF = 1e9 + 10; const double eps = 1e-10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, to[MAXN]; double f[MAXN]; int main() { while(scanf("%d %d", &N, &M)) { if((N == 0) && (M == 0)) break; memset(to, 0, sizeof(to)); memset(f, 0, sizeof(f)); for(int i = 1; i <= M; i++) { int x = read(), y = read(); to[x] = y; } for(int x = N - 1; x >= 0; x--) { if(to[x]) f[x] = f[to[x]]; else { for(int j = 1; j <= 6; j++) f[x] += f[x + j]; f[x] /= 6; f[x]++; } } printf("%.4lf\n", f[0]); } return 0; } /* */