Codeforces 1245 E. Hyakugoku and Ladders

显然这个图是个 $DAG$ ，那么就可以考虑跑 $dp$ 了

先考虑没有梯子的情况，首先把每个位置标号，越后面的位置编号越小，终点位置编号为 $1$

那么从终点往起点 $dp$ ，枚举当前位置摇到的数字，那么有 $f[x]=\frac{\sum_{i=1}^{6}(f[x-i]+1)}{6}$，并且 $f[1]=0$

但是这是在 $x>6$ 的情况下成立的，因为如果 $x<=6$ 那么有可能不走，特殊考虑一下

首先 $f[2]$ ，那么有 $5/6$ 的概率原地不动，$1/6$ 的概率走到终点，即 $f[2]=\frac{5(f[2]+1)}{6}+\frac{f[1]+1}{6}=(\frac{5}{6}+\frac{f[1]+1}{6}) / (1-5/6)$

然后 $f[3]$ 也差不多考虑，$f[3]=\frac{4(f[3]+1)}{6}+\frac{f[1]+1}{6}+\frac{f[2]+1}{6}=(\frac{4}{6}+\frac{f[1]+1}{6}+\frac{f[2]+1}{6}) / (1-4/6)$

发现对于 $x\in [2,6]$ ，$f[x]=\frac{(\sum_{i=1}^{x-1}f[x-i]+1)/6+(7-i)/6}{1-(7-i)/6}$

现在来考虑有梯子的情况，设位置 $x$ 有一个梯子通往位置 $y$ ，那么 $f[x]$ 转移的时候还要考虑瞬移到 $y$ 再走的情况

差不多的转移，取个最小值即可，即和 $\sum_{i=1}^{6}(f[y-i]+1)/6$ 取个最小值，对于 $y<=6$ 的情况同样要特殊处理

看代码就知道具体怎么做了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

typedef double db;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int n=,N=;

int id[N][N],to[N];

db f[N];

int main()

{

    int tot=;

    for(int i=;i<=n;i++)

    {

        if(i&)

            for(int j=;j<=n;j++)

                id[i][j]=++tot;

        else

            for(int j=n;j>=;j--)

                id[i][j]=++tot;

    }

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

        {

            int a=read();

            if(a) to[id[i][j]]=id[i-a][j];

        }

    // f[2]=(f[2]+1)*5/6 + 1/6

    // f[3]=(f[3]+1)*4/6 + 1/6 + (f[2]+1)/6

    for(int i=;i<=;i++)

    {

        for(int j=;j<i;j++)

            f[i]+=(f[i-j]+1.0)/;

        f[i]+=(7.0-i)/;

        f[i]/=(1.0-(7.0-i)/);

    }

    for(int i=;i<=tot;i++)

    {

        for(int j=;j<=;j++)

            f[i]+=(f[i-j]+1.0)/;

        if(!to[i]) continue;

        db mi=; int t=to[i];

        if(t==) { f[i]=; continue; }//我这个做法要特判

        for(int j=;j<=;j++)

            if(t-j>) mi+=(f[t-j]+1.0)/;

        if(t<=) mi+=(7.0-t)/,mi/=(1.0-(7.0-t)/);

        f[i]=min(f[i],mi);

    }

    printf("%.10f\n",f[tot]);

    return ;

}

巴特西

Codeforces 1245 E. Hyakugoku and Ladders

最新文章

热门文章