这个模型跟小时候玩的大富翁棋类游戏差不多，起点是0，终点是N，每次掷骰子走1~6步，格子分为3种，前进1~6格，后退1~6格，以及停止一回合，求到达终点所需回合数的期望。
用E(I)表示从第I个格子走到终点所需回合的期望，E(N)=0，转移方程为 E(I)=sum(1/6*(E(K1)+1))+sum(1/6*(E(K2)+2))。K1,K2都是从I掷1~6能走到的格子，如果这个格子有操作，就要跳到操作后的格子，第一个sum里求的是不会停一回合的期望和，第二个sum里求的是走到停一回合格子的期望和。
因为有后退操作，所以转移是有环的，不能用记忆化搜索，要用高斯消元来做。
一开始可以DFS一遍标记所以能到达的格子，这样可以直接判断是否有解。对于不可达的点，也不需要去消元。
比较蛋疼的是遇到端点折回的情况，比如在N=2时，在1掷了个5，那路线就是1->2->1->0->1->2。。没总结出用什么式子算，索性写了个暴力模拟一直调整直到到达0~N的范围中。。
这题精度比较低，暴力的循环DP1000次貌似也能过。。我本机随机数据测了一下，暴力DP的精度还是有限的，2位的精度基本都对上了，但位数再高一点精度就差不少了，所以这类题最好还是高斯消元解吧，反正也不麻烦。
1 #include2 #include 3 #include 4 #include 5 #define MAXN 105 6 #define INF 0x3f3f3f3f 7 #define eps 1e-9 8 using namespace std; 9 int n, nf, tx, ty; 10 int reach[MAXN], fp[MAXN], id[MAXN], ids; 11 double x[MAXN][MAXN], ans[MAXN]; 12 double gauss(int n,int m) { 13 int row = 0, col = 0; 14 for (;row < n && col < m; col++) { 15 int maxr = row; 16 for (int i = row+1; i < n; i++) 17 if (fabs(x[i][col]) > fabs(x[maxr][col]))maxr = i; 18 if (fabs(x[maxr][col]) < eps) continue; 19 if (maxr != row) for (int i = 0; i <= m; i++) swap(x[row][i], x[maxr][i]); 20 for (int k1 = row+1; k1 < n; k1++) { 21 double div = x[k1][col] / x[row][col]; 22 for (int k2 = col; k2 <= m; k2++) { 23 x[k1][k2] -= div * x[row][k2]; 24 } 25 } 26 row++; 27 } 28 memset(ans, 0, sizeof ans); 29 for (int i = n-1; i >= 0; i--) { 30 double tmp = 0; 31 for (int j = i+1; j < m; j++) 32 tmp += ans[j] * x[i][j]; 33 ans[i] = (- x[i][m] - tmp) / x[i][i]; 34 } 35 return ans[0]; 36 } 37 int getnp(int p,int i) { 38 int np = i+p; 39 while (np < 0 || np > n) np = np > n ? 2*n-np : -np; 40 return np; 41 } 42 void dfsreach(int p) { 43 reach[p] = 1; 44 for (int i = 1;i <= 6; i++) { 45 int np = getnp(p, i); 46 if (fp[np] != INF) np = getnp(np, fp[np]); 47 if (!reach[np]) dfsreach(np); 48 } 49 } 50 void solve() { 51 memset(reach, 0 ,sizeof reach); 52 dfsreach(0); 53 if (reach[n] == 0) { 54 printf("Impossible\n"); 55 return; 56 } 57 ids = 0; 58 double one = 1.0/6.0; 59 for (int i = 0; i < n; i++) if (reach[i]) id[i] = ids++; 60 memset(x, 0, sizeof x); 61 for (int p = 0; p < n; p++) { 62 if (reach[p] == 0) continue; 63 x[id[p]][id[p]] = -1; 64 for (int i = 1; i <= 6; i++) { 65 int np = getnp(p, i), nfp = fp[np]; 66 if (fp[np] != INF) np = getnp(np, fp[np]); 67 //已经到达终点 68 if (np == n) { 69 x[id[p]][ids] += one; 70 //注意,是第一步跳到了停止上才是停止 71 } else if(nfp == 0) { 72 x[id[p]][id[np]] += one; 73 x[id[p]][ids] += one * 2; 74 } else { 75 x[id[p]][id[np]] += one; 76 x[id[p]][ids] += one; 77 } 78 } 79 } 80 double x = gauss(ids, ids); 81 printf("%.2f\n", x); 82 } 83 int main(){ 84 freopen("test.in","r",stdin); 85 freopen("test.out","w",stdout); 86 while (scanf("%d", &n) != EOF) { 87 scanf("%d", &nf); 88 memset(fp, 0x3f, sizeof fp); 89 for (int i = 0; i < nf; i++) 90 scanf("%d%d", &tx, &ty), fp[tx] = ty; 91 scanf("%d", &nf); 92 for (int i = 0; i < nf; i++) 93 scanf("%d%d", &tx, &ty), fp[tx] = -ty; 94 scanf("%d", &nf); 95 for (int i = 0; i < nf; i++) 96 scanf("%d", &tx), fp[tx] = 0; 97 solve(); 98 } 99 return 0;100 }