# Hdu4405 aeroplane chess (expected dp)

## 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;
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++) {
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);
}
return 0;
}
/*

*/```

Keywords: C++

Added by salomo on Mon, 06 Jan 2020 17:10:38 +0200