POJ 3744 Scout YYF I

题意

某人在直线上走,直线上有若干格子,起点是1号格,每次这个人都有p概率走1格,1-p概率走二格,有一些格子有地雷,走上去就被爆了,所以要你求你能安全走到终点(可以看成是站在n+1号格)上概率。

思路

每一个格子的概率都可以通过它前两个的格子的概率推出来,这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么?快速幂。
所以这个题我们用快速幂来做。

dp方程其实都不叫dp,叫递推,大概长这个样子:

\begin{bmatrix}p&1-p\\1&0 \end{bmatrix}\begin{bmatrix}p_{n} \\ p_{n-1}\end{bmatrix}=\begin{bmatrix} p_{n+1}\\p_{n}\end{bmatrix}

直接矩阵乘法模版+快速幂就行。

处理地雷的话,你就先走到地雷那里,停一下,把地雷格的dp值抹成0,然后继续往下走,走到下一个地雷,最后走到终点。

代码

 

Codeforces 118D Caesar's Legions

题意

给你两种士兵,n1个A和n2个B,同种士兵是一样的,不分先后,然后你最多能把k1个A排到一起k2个B排到一起,问你有多少种有效排法。

思路

动态规划,建一个三维dp数组,其实是一个二维的表,每个格子有两个值,dp[i][j]表示截至目前只使用i个A,j个B来进行排列,dp[i][j][0]表示以A结尾的排列序列个数,dp[i][j][1]表示以B结尾的排列序列个数,之后我们来转移状态,对于当前的以A结尾的排列,我们可以再其末尾加1~k2个B,构成新的以B结尾的排列,所以我们就可以把dp[i][j+k][1]更新了(k表示加几个B)。同样的,用B结尾排列个数的值更新之后的A结尾排列个数的值,把这个表这样逐步打好,最后输出dp[n1][n2][0]+dp[n1][n2][1]即可。

接下来上代码

 

Scroll to top