|
|
思路：
方程：
f[i][j] = { 還剩 i 次投 dice 的機會，此時位于第 j 個格子。這種情況下贏的概率 }
狀態轉移：
現在投 dice。分別考慮投到 1~6 的情況，假設最后停在 k 點。
如果 k 點是 L 點。則概率 g = f[i - 2][j]
如果 k 點是 B 點。則概率 g = f[i - 1][0]
如果 k 點是一個普通的點，則概率 g = f[i - 1][j]
f[i][j] = g[1]/6 + g[2]/6 + ... + g[6]/6
代碼：
 #include <stdio.h>
#include <string.h>
double prob[3][128], *p[3];
int N, T, L, B;
char map[128];
inline double calc(int x)
   {
  switch (map[x]) {
 case 'B': return p[1][0];
case 'L': return p[0][x];
default : return p[1][x];
 }
 }
int main()
{
int i, j, c, x;
freopen("e:\\test\\in.txt", "r", stdin);
while (scanf("%d%d%d%d", &N, &T, &L, &B), N) {
memset(map, ' ', sizeof(map));
memset(prob, 0, sizeof(prob));
while (L--) {
scanf("%d", &i);
map[i] = 'L';
}
while (B--) {
scanf("%d", &i);
map[i] = 'B';
}
//prob[1][N] = 1;
for (i = 0; i < T; i++) {
p[2] = prob[(i+2)%3];
p[1] = prob[(i+1)%3];
p[0] = prob[i%3];
p[1][N] = 1;
for (j = 0; j < N; j++) {
p[2][j] = 0;
for (c = 6, x = j + 1; c && x < N; c--, x++)
p[2][j] += calc(x) / 6;
for ( ; c; c--, x--)
p[2][j] += calc(x) / 6;
}
}
printf("%.6lf\n", p[2][0]);
}
return 0;
}
|