C/C++教程

UVA580 危险的组合 Critical Mass

本文主要是介绍UVA580 危险的组合 Critical Mass，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

DP做法：转移的时候只要考虑最后有几个连续的铀盒或者是否已经满足条件。

所以用 $dp_{i,j}$ 表示有考虑了前 $i$ 个盒子，最后有 $j$ 个连续铀盒的方案数。特殊地，当 $j = m$ 时表示前 $i$ 个盒子已经有了连续 $m$ 个铀盒的方案数，其中 $m$ 为需要的连续铀盒数，题目中， $m = 3$。

转移方程：$\begin{cases} dp_{0,0}=1 \\ dp_{i,0} = \sum ^{m-1} _{j = 0} dp_{i-1,j} \\ dp_{i,j} = dp_{i-1,j-1} \\ dp_{i,m} = 2dp_{i-1,m} + dp_{i-1,m-1}\end{cases}$

时间复杂度 $O(nm)$

不难发现 $dp_{i,j}=dp_{i-j,0}$ ，则 $
\begin{cases} dp_{0,0} = dp_{1,0} = 1 \\ dp_{i,0} = 2dp_{i-1,0}-dp_{i-m-1,0} \\ dp_{i,m} = 2dp_{i-1,m} + dp_{i-m,0}\end{cases}$

时间复杂度 $O(n)$

递推做法，$f(n) = 2^{n-3} + \sum ^{n-3}_{i=0} 2^{n-i-3}f(i)$

这篇关于UVA580 危险的组合 Critical Mass的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航