问题描述

一个核电站有n个放核物质的坑，排列在一条直线上。如果连续m个坑中放入核物质就会发生爆炸，所以某些坑中不能放核物质。

本题的任务：对于给定的n和m，求不发生爆炸的放置核物质的方案总数。

输入格式

第一行两个正整数n和m，之间用一个空格隔开。2≤n≤50,2≤m≤5。

输出格式

一行一个正整数，表示方案总数。

输入样例

4 3

输出样例

13

数据规模与约定

2≤n≤50,2≤m≤5

CODE

#includeusing namespace std;long long n,m,dp[55];int main(){cin>>n>>m;dp[0]=1;for(int i=1;i<m;i++) dp[i]=dp[i-1]*2;dp[m]=dp[m-1]*2-1;for(int i=m+1;i<=n;i++) dp[i]=dp[i-1]*2-dp[i-m-1];cout<<dp[n];return 0;}

#include using namespace std;int n,m;long long dp[100];int main(){cin>>n>>m;dp[0]=1;for(int i=1;i<=n;i++){if(i<m){dp[i]=dp[i-1]*2;}else if(i==m){dp[i]=dp[i-1]*2-1;}else{dp[i]=dp[i-1]*2-dp[i-m-1];}}cout<<dp[n]<<endl;return 0;}

天天赞天天看，关注我!

明天再见，拜拜！

51mike麦克疯