CF1245E Hyakugoku and Ladders

---

一道不错的概率dp

---

题解：

方便起见，先将二维转成一维，终点为100,起点为1

设f[i]表示格子i到终点的期望步数，nxt[i]表示用梯子会到达的格子

初始f[100]=0

先考虑不能一步到的格子（93～1），转移为$f[i]=1+\frac{\sum_{j=1}^{6} \min(f[i+j],f[nxt[i+j]])}{6}$

（解释：+1表示要在上一种基础上多扔一次，除以6表示从每个上一种转移的概率都是$\frac{1}{6}$，min()表示可以靠老老实实走转移，也可以靠梯子转移）

再考虑能一步到的格子（99～94）

手算

$$f[99]=\frac{5(f[99]+1)}{6}+\frac{f[100]+1}{6}$$

（解释：$\frac{5}{6}$概率留原地,$\frac{1}{6}$概率到终点）

打开

$$\frac{f[99]}{6}=1$$

得到

$$f[99]=6$$

其他同理，可以得出99~94号格子都期望6步到达终点

最后答案就是f[1]

---

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=15;
int id[N][N],nxt[105],cnt;
double f[105];

signed main(){
    for(int i=10;i>=1;i--)
        if(i&1)
            for(int j=10;j>=1;j--) id[i][j]=++cnt;
        else
            for(int j=1;j<=10;j++) id[i][j]=++cnt; //id[i][j]表示从上到下第i行，从左到右第j列转成一维后的序号
    for(int i=1,x;i<=10;i++)
        for(int j=1;j<=10;j++)
            nxt[id[i][j]]=id[i-read(x)][j]; //nxt[i]表示第i格子会到哪，有梯子则指向梯子终点，否则指向自己
    for(int i=99;i>=94;i--) f[i]=6; //手算得出
    for(int i=93;i>=1;i--){
        for(int j=1;j<=6;j++)
            f[i]+=fmin(f[i+j],f[nxt[i+j]]); //转移
        f[i]=f[i]/6.0+1; //除以概率，加上代价
    }
    printf("%.10lf",f[1]);
}