首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7435

核电站 一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。 任务:对于给定的N和M,求…

核电站

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

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

时间限制:6000

内存限制:131072

输入

只一行,两个正整数N,M( 1 < N < 50,2 ≤ M ≤ 5 )

输出

一个正整数S,表示方案总数。

样例输入

4 3

样例输出

13
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//样例代码  动态规划 #include &lt;bits/stdc++.h&gt; using namespace std; int n,m; long long dp[55][7];//前i个坑现在已经连续埋了j个的方案 int main() { cin&gt;&gt;n&gt;&gt;m; dp[1][1]=1;//第1个放 dp[1][0]=1;//第1个不放 for(int i=2;i&lt;=n;i++){ for(int j=0;j&lt;m;j++){ if(j==0){//第j个不放 for(int k=0;k&lt;m;k++)//0~m-1的位置都可放可不放 dp[i][j]+=dp[i-1][k]; } else //第j个放 dp[i][j]+=dp[i-1][j-1]; } } long long ans=0; for(int i=0;i&lt;m;i++) ans+=dp[n][i]; cout&lt;&lt;ans; return 0; }</pre><p><br/></p>
这道题暂未补解析。