0%

CF1245E

CF1245E

题意:给一个棋盘,有10行10列。格子上可能有梯子,能通过梯子爬到上方的某个格子。但不能连续爬,即通过梯子到达一个格子后不能爬这个格子上的梯子。有一个均匀的6面骰子,求到终点的最小期望投骰子次数。(我概括的不好,有些细节没有提到,建议还是自己读题)

解:先给每个格子分配一个编号,便于处理.我记终点为1,然后按顺序标号,起点为100.同时处理出$to(i)$表示在$i$处爬梯子会爬到的格子编号(若没有梯子,$to(i)=i$)

考虑期望dp.记$f(i)$表示$i$到终点的期望.显然$f(1)=0$,$f(100)$即为答案.

对于$i\ge95$,可能会越过终点.对于超出部分,期望就是$f(i)$,否则是$f(i-j),j$是这次的数,即

接下来考虑一般的格子,这些格子可能有梯子,但不会超出.

注意,在通过梯子爬到一个格子$x$后,不能再爬$x$这里的梯子了,因此这样是错的:

因此$f(i)$应严谨地定义为从$i$到终点,且$i$处不爬梯子的期望.对于走到的点是可以走梯子的,即:

时间复杂度$O(nmk)$,此处$n=m=10,k=6$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**********/
#define MAXN 15
ll num[MAXN][MAXN],to[MAXN*MAXN];//编号,梯子到达的点的编号
double f[MAXN*MAXN];//f
int main()
{
for(ll i=1;i<=10;++i)
for(ll j=1;j<=10;++j)
{
ll h=read(),&cur=num[i][j];
if(i&1)cur=(i-1)*10+j;
else cur=i*10-j+1;
to[cur]=num[i-h][j];
}
f[1]=0;
for(ll i=2;i<=100;++i)
{
if(i<=6)
{
double s=1;
for(ll j=1;j<i;++j)s+=f[i-j]/6;
f[i]=6*s/(i-1);
}
else
{
double s=1;
for(ll j=1;j<=6;++j)s+=std::min(f[i-j],f[to[i-j]])/6;
f[i]=s;
}
}
printf("%.6f",f[100]);
}