松原市城乡建设局网站wordpress竞争

T1. 酒鬼

此题为 2021 年 3 月四级第一题原题，见 2021 年 3 月青少年软编等考 C 语言四级真题解析中的 T1。

T2. 大盗

此题为 2021 年 6 月四级第二题原题，见 2021 年 6 月青少年软编等考 C 语言四级真题解析中的 T2。

T3. 核电站

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

任务：对于给定的 $N$ 和 $M$，求不发生爆炸的放置核物质的方案总数。

时间限制：6 s
内存限制：128 MB

• 输入
  只有一行，两个正整数 $N$，$M(1<N<50，2\le M\le 5)$。
• 输出
  一个正整数 $S$，表示方案总数。
• 样例输入

  4 3
  

• 样例输出

  13
  

思路分析

此题考查动态规划，有一定难度。

定义 $f_{i,0}$ 表示第 $i$ 个坑不放核物质的方案数，$f_{i,1}$ 表示第 $i$ 个坑放核物质的方案数，于是 $f_{i,0}=f_{i-1,0}+f_{i-1,1}$，$f_{i,1}$ 的情况稍微复杂一些

• 当 $i<m$ 时，$f_{i,1}=f_{i,0}$；
• 当 i = m i = m i=m<