题目描述：

类似大富翁的游戏，给你一条长度为n的条状棋盘，起点为0号，终点为n号，一共有n 1个点。

每个点有4种状态：

1：无状态。

2：从此点往前走k步。

3：从此点往后退m步。

4：下一回合不能动。

每一回合仅能启用一种状态（比如中了状态2往前走k步后，刚好又碰到状态3，则状态3不起作用）

如果退到0点或者n点还有剩余的步可以走，则往相反的方向走（既不能丢弃多余的步，也不能走出棋盘）。

问你从0走到n所需的回合的期望。

解题报告：

dp，dp[i][j]表示第i回合走到第j号点的概率是多少，开始时dp[0][0] = 1,其他都为0.

若dp[i][j] != 0， 根据规则，容易求的从j开始抛骰子的以下六个位置记作pos[k]， 0<= k < 6

如果走到pos[k]是启用的是状态4（下一回合不能动）

则dp[i 2][pos[k]] = dp[i][j] * (1 / 6)

否则 dp[i 1][pos[k]] = dp[i][j] * (1 / 6)

最后则求各个dp[i][n]的概率乘以i 的和即可得到回合期望。

由于精度要求小数点后2位，所以i值的最大值需要自己确定，在不超时的情况下尽量精确。

数据貌似很弱，i最大取去200即可。

代码如下：

#include<iostream>
using namespace std;
#define MAX_ROUND 200
#define SIZE 101
int n, nf, nb, ns, path[SIZE][2], pos;
double dp[MAX_ROUND 2][SIZE], ans;
void input(int n, int type)
{
    for(int i = 0; i < n; i )
    {
        scanf("%d", &pos);
        path[pos][0] = type;
        if (type != 3) scanf("%d", &path[pos][1]);
        if (type == 2)
            path[pos][1] = -path[pos][1];
    }
}
int GetPos(int pos)
{
    while(true)
        if (pos < 0) pos = -pos;
        else if (pos > n) pos = n n - pos;
        else return pos;
}
int main()
{
    scanf("%d", &n);
    memset(path, 0, sizeof(path));memset(dp, 0, sizeof(dp));
    scanf("%d", &nf);input(nf, 1);
    scanf("%d", &nb);input(nb, 2);
    scanf("%d", &ns);input(ns, 3);
    double each = 1.0 / 6.0; pos = 0; dp[0][0] = 1;ans = 0;
    for(int i = 0; i < MAX_ROUND; i )
        for(int j = 0; j < n; j )
            if (dp[i][j] > 0)
                for(int k = 1; k <= 6; k )
                {
                    int next = GetPos(j k);
                    if (path[next][0] == 3)
                        dp[i 2][next] = dp[i][j] * each;
                    else
                    {
                        next = GetPos(next path[next][1]);
                        dp[i 1][next] = dp[i][j] * each;
                    }
                }
    for(int i = 0; i <= MAX_ROUND; i )
        ans = dp[i][n] * i;
    if (ans == 0)
        printf("Impossible\n");
    else
        printf("%.2f\n", ans);
    return 0;
}