【2018SCUACM Wednesday 6 DP】

题目来源

A:CodeForces 540D

B:CodeForces 571B

C:CodeForces 570E

D:CodeForces 533E

解题报告

A:简单概率DP,设\(dp[i][j][k]\)表示石头有\(i\)个,剪刀有\(j\)个,布有\(k\)个的概率,此时,相遇共有三种情况(此题题意应为同种族人不相遇):

①石头遇到剪刀,此种概率数量为\(i*j\),且之后\(j=j-1\)。

②剪刀遇到布,此种概率数量为\(j*k\),且之后\(k=k-1\)。

③布遇到石头,此种概率数量为\(k*i\),且之后\(i=i-1\)。

不难得出,总的情况数量为\(i*j+j*k+k*i\)。

所以,①对应概率为\(A=\frac{i*j}{i*j+j*k+k*i}\);②对应概率为\(B=\frac{j*k}{i*j+j*k+k*i}\);③对应概率为\(C=\frac{k*i}{i*j+j*k+k*i}\)

据此,我们即可得出状态转移方程式:

若\(i\ge 1,k\ge 1\),则\(dp[i-1][j][k]=C*dp[i][j][k]\)

若\(j\ge 1,i\ge 1\),则\(dp[i][j-1][k]=A*dp[i][j][k]\)

若\(k\ge 1,j\ge 1\),则\(dp[i][j][k-1]=B*dp[i][j][k]\)

最终答案\(ansR=\sum\limits_{i=1}^{r}dp[i][0][0]\),\(ansS=\sum\limits_{i=1}^{s}dp[0][i][0]\),\(ansP=\sum\limits_{i=1}^{p}dp[0][0][i]\)

C:滚动数组+双路DP。由于回文串一定是对称的,我们首先不难想到一个四维DP:\(dp[x_1][y_1][x_2][y_2]\)表示左上角走到\((x_1,y_1)\),右下角走到\((x_2,y_2)\)时的合法方案数。然而,由于\(n,m\le 500\),这么做无疑会MLE。转念一想,只要知道了步数,知道了\(x_1\)、\(x_2\),不就可以直接求出\(y_1\)和\(y_2\)了么?因此可以降去两维\(y_1\)和\(y_2\)并且添上一维\(step\)表示走了\(step\)步时的的状态。

但是这道题就算这么降维,还是会MLE,于是必须得进一步优化空间。注意到当前步只可能由上一步的状态推导出,由此我们实际上第一维\(step\)只用保留两步的状态即可,所以直接把第一维滚动就行。

至于求\(y_1\)和\(y_2\),我们设第\(0\)步两点分别位于\((1,1)\)与\((n,m)\),则有:
\(
\begin{equation}
\left\{
\begin{array}{lr}
x_1+y_1-2=step & & \\
x_2+y_2+step=n+m
\end{array}
\right.
\end{equation}
\) \(\Rightarrow\)          \(
\begin{equation}
\left\{
\begin{array}{lr}
y_1=step-x_1+2 & & \\
y_2=n+m-step-x_2
\end{array}
\right.
\end{equation}
\)

转移时注意判断\((x_1,y_1)\)是否在\((x_2,y_2)\)左上角。

值得一提的一点是,如果回文串长度为奇数,最终两点肯定会走到一起(奇数回文串中心位置),但是长度为偶数的情况就不一定了(参考样例的第三种情况,最终左上角的点走到了\((1,3)\)而右下角的点走到了\((2,3)\)),这种情况下我们还要单独计算一下答案。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*