CF1245E：Hyakugoku and Ladders

题意描述：

给你一个\(10*10\)的矩阵，矩阵描述如下
- 最开始的时候你在左下角，你的目标是到达左上角。
- 你可以走路径或者爬梯子。
- 路径的定义：
  - 如果当前在一行的最右边，你可以网上爬一格。
  - 如果在行内其他位置，你可以往旁边走。
- 每一回合你都要掷一个六面的骰子，假设当前骰子的正面为\(r\)。如果到终点的距离小于\(r\)，那么你将不能移动。否则你将移动\(r\)格，如果你最后移动到的位置有一个梯子，你可以选择爬上去或者不怕上去。
你的目标是找到到达目的的回合的最小期望。

思路：

期望\(dp\)。
在二维上不是很方便，我们可以把二维看成一个一维数组。
\(f(i)\)表示到\(i\)需要多少回合。如果没有梯子的限制，那么有状态转移方程：
- \(f(i)=\frac{f(i-1)+f(i-2)+...+f(i-6)}{6}+1\)
那么有了梯子，我们只需要针对梯子转移过来的情况取\(min\)即可。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 15;

int g[maxn][maxn];

int nex[maxn][maxn];

int a[maxn*maxn];

double f[maxn*maxn];

int main()

{

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

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

            nex[i][j] = (i-1)*10 + (i&1 ? j : 11-j);

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

        for(int j = 1, x; j <= 10; j++){

            scanf("%d", &x);

            a[nex[i][j]] = nex[i-x][j];

        }

    f[1] = 0;

    double sum = 0;

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

        f[i] = (sum+6) / (i-1), sum += f[i];

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

    {

        sum = 0;

        for(int r = 1; r <= 6; r++)

            sum = sum + min(f[i-r], f[a[i-r]]);

        f[i] = sum / 6.0 + 1;

    }

    printf("%.10f", f[100]);

    return 0;

}

巴特西

CF1245E：Hyakugoku and Ladders

CF1245E：Hyakugoku and Ladders

题意描述：

思路：

最新文章

热门文章