pascal语言组合方块
答案:1 悬赏:20 手机版
解决时间 2021-02-26 07:07
- 提问者网友：未信
- 2021-02-25 06:21
pascal语言组合方块
最佳答案
- 五星知识达人网友：雾月
- 2021-02-25 07:55
我们可以用DP来做这题。
这题可以转化为将n个方块分为任意堆，使每堆的和都是质数的方案数。
设f[i,j]为前i个方块分为j堆，每堆的和都是质数的方案数。
设sum[i]为前i个方块的和
可以得出方程：f[i,j]=Σ（f[k,j-1]）（k∈[1,i-1]，且sum[i]-sum[k]为质数）
但这样直接做要判断很多次素数，很可能超时。
我们发现即使1000个方块编号都是1000和也只有一百万，我们可以用线性筛找出1到一百万的素数，这样判断就只需要O（1）了。
然而这样复杂度也是O（n^3）。
我们可以先对每一个i预处理出满足sum[i]-sum[k]为质数的k，实际上这种k不会很多，所以DP时只是比O（n^2）稍慢一点，不影响时间。
程序就不写了，有需要的话请追问。
这题可以转化为将n个方块分为任意堆，使每堆的和都是质数的方案数。
设f[i,j]为前i个方块分为j堆，每堆的和都是质数的方案数。
设sum[i]为前i个方块的和
可以得出方程：f[i,j]=Σ（f[k,j-1]）（k∈[1,i-1]，且sum[i]-sum[k]为质数）
但这样直接做要判断很多次素数，很可能超时。
我们发现即使1000个方块编号都是1000和也只有一百万，我们可以用线性筛找出1到一百万的素数，这样判断就只需要O（1）了。
然而这样复杂度也是O（n^3）。
我们可以先对每一个i预处理出满足sum[i]-sum[k]为质数的k，实际上这种k不会很多，所以DP时只是比O（n^2）稍慢一点，不影响时间。
程序就不写了，有需要的话请追问。
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯