2012-0001

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

zhan by 大肥羊～此坑必填@.@


这题的一个直观的想法是二维dp[i][j],i表示当前在第i个格子，j表示当前分数为j，但是分数的范围就有10^6^，这样必定超时

考虑到每次分数变化都是取最小公倍数，而且不能相同，所以每走一步，分数必定增加，而且无论何时，分数都一定是最终目标K的约数

所以虽然K的范围是10^6^，但K的约数个数在10^3^左右，只有约数的分数状态是有意义的，将K的所有约数排序之后，于是dp[i][j]的第二维j就可以表示成当前分数为K的第几个约数

然后就变成一个很简单的dp了，根据每个格子延伸出去的边进行转移即可，如果新的分数不是K的约数，或者超过了K，都无法转移

zhan by 大肥羊～此坑必填@.@

这题的一个直观的想法是二维dp[i][j],i表示当前在第i个格子，j表示当前分数为j，但是分数的范围就有10⁶，这样必定超时

考虑到每次分数变化都是取最小公倍数，而且不能相同，所以每走一步，分数必定增加，而且无论何时，分数都一定是最终目标K的约数

所以虽然K的范围是10⁶，但K的约数个数在10³左右，只有约数的分数状态是有意义的，将K的所有约数排序之后，于是dp[i][j]的第二维j就可以表示成当前分数为K的第几个约数

然后就变成一个很简单的dp了，根据每个格子延伸出去的边进行转移即可，如果新的分数不是K的约数，或者超过了K，都无法转移