Codeforces

Luogu

完了我期望都不会算了 /dk

分析

先把走过的点依次编号 $100\cdots 1$,起点为 $100$,终点为 $1$。再设 $to_i$ 表示 $i$ 爬梯子能到的点。

考虑 DP。设 $dp_i$ 表示 $i$ 到 $1$ 的期望步数。

当 $2\leq i\leq 6$时,状态转移方程为

$$ dp_i=\frac{6}{i-1}\left(1+\sum_{j=1}^{i-1}\frac{dp_j}{6}\right) $$

当 $7\leq i\leq 100$ 时,状态转移方程为

$$ dp_i=1+\frac{1}{6}\left(\sum_{j=1}^6\min\left\{dp_{i-j},dp_{to_{i-j}}\right\}\right) $$

答案为 $dp_{100}$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;

inline int id(int x,int y) {
    if (x&1) return (x-1)*10+y;
    else return (x-1)*10+11-y;
}

int to[N]; double dp[N];

int main() {
    for (re int i=1;i<=10;++i)
        for (re int j=1;j<=10;++j)
            to[id(i,j)]=id(i-read(),j);
    for (re int i=2;i<=6;++i) {
        for (re int j=1;j<i;++j) dp[i]+=dp[j]/6;
        dp[i]=(dp[i]+1)/(i-1)*6;
    }
    for (re int i=7;i<=100;++i) {
        for (re int j=1;j<=6;++j) dp[i]+=min(dp[i-j],dp[to[i-j]]);
        dp[i]=dp[i]/6+1;
    }
    printf("%.10lf\n",dp[100]);
    return 0;
}
最后修改:2019 年 11 月 15 日 04 : 04 PM