刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

核电站
一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。

任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数
时间限制：6000
内存限制：131072
输入
只一行，两个正整数N，M( 1 < N < 50，2 ≤ M ≤ 5 )
输出
一个正整数S，表示方案总数。
样例输入

4 3

样例输出

13

使用微信搜索喵呜刷题，轻松应对考试！

答案：

无

解析：

【喵呜刷题小喵解析】这是一个典型的动态规划问题。我们定义一个dp数组，dp[i]表示前i个坑不发生爆炸的放置核物质的方案总数。首先，我们初始化dp[0] = 1，因为前0个坑无论如何放置都不会发生爆炸，只有一种方案，即不放置核物质。然后，我们从第1个坑开始，逐个计算dp数组。对于每个i（1 ≤ i ≤ N），dp[i]有两种情况：1. 前i-1个坑不发生爆炸的方案数，即dp[i-1]。2. 如果i >= M，前i-M个坑也不发生爆炸的方案数，即dp[i-M]。因为连续M个坑中放入核物质会发生爆炸，所以第i个坑之前必须至少有M-1个坑不放核物质，才能保证前i个坑不发生爆炸。最后，dp[N]就是前N个坑不发生爆炸的放置核物质的方案总数，即输出dp[N]。在这个程序中，我们使用map函数将输入的两个整数N和M从字符串转换为整数，然后使用print函数输出dp[N]。
创作类型：
原创

本文链接：核电站 一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share