简答题
偏难
#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 <bits/stdc++.h>
using namespace std;
int n,m;
long long dp[55][7];//前i个坑现在已经连续埋了j个的方案
int main()
{
cin>>n>>m;
dp[1][1]=1;//第1个放
dp[1][0]=1;//第1个不放
for(int i=2;i<=n;i++){
for(int j=0;j<m;j++){
if(j==0){//第j个不放
for(int k=0;k<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<m;i++)
ans+=dp[n][i];
cout<<ans;
return 0;
}</pre><p><br/></p>
这道题暂未补解析。