AtCoder ABC 266 复盘

标签：AtCoder AC ABC dfrac Code text 266 max dp

A Middle Letter

水沝淼㵘纯模拟题。根据题意，易得答案。

AC Code

B Modulo Number

模拟（+数学？）。先 \(N\leftarrow N\bmod 998244353\)，然后 \(N\leftarrow N+998244353\ (N<0)\)，最后输出 \(N\)。

AC Code

C Convex Quadrilateral

数学。有一个公式判断（名字我忘了）可以判断。详见 AC Code。

D Snuke Panic (1D)

DP 经典永流传。

设 $dp[x][t] = $ 高桥在 \(t\) 时刻到达坐标 \(x\) 之前捕获的 Snukes 的数量总和的最大值，则有转移方程为：

\[dp[x][t]=\max(dp[x-1][t-1],dp[x][t-1],dp[x+1][t-1])+\text{当他于}\ t\ \text{时刻在坐标}\ x\ \text{处时，他可以捕获的 Snukes 的数量} \]

AC Code

E Throwing the Die

首先我们需要知道，什么是 expected value（期望值）。

什么是期望值？

期望值是指对于某个随机事件，所有可能结果的加权平均数，其中每个结果的权重是其发生的概率。通俗点讲，期望值可以理解为一个事件在多次试验中出现的平均次数。

在继续游戏时，目前的结果不会影响得分，因此预期值只取决于我们还多掷几次骰子。

如果我们多掷骰子 \(X\) 次，那么 \(f(X)\) 就是最大的预期得分。当骰子朝上的一面是 \(R\) 时，如果我们退出游戏，我们可以获得 \(R\) 分；否则，我们可以获得 \(f(X-1)\) 分。当 \(X=0\) 时，\(f(X)=0\)。由此可以得到计算公式：

\[f(X) = \begin{cases}0&X=0\\\dfrac{1}{6}\max(1,f(X-1))+\dfrac{1}{6}\max(2,f(X-1))+\dfrac{1}{6}\max(3,f(X-1))+\dfrac{1}{6}\max(4,f(X-1))+\dfrac{1}{6}\max(5,f(X-1))+\dfrac{1}{6}\max(6,f(X-1))&\text{otherwise}\end{cases} \]

答案即为 \(f(N)\)。

思考一下，我们即可想出非递归写法。

标签：AtCoder,AC,ABC,dfrac,Code,text,266,max,dp
From： https://www.cnblogs.com/TigerTanWQY/p/17986164