Vijos 1232 核电站问题

核电站问题

描述

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

现在，请你计算：对于给定的N和M，求不发生爆炸的放置核物质的方案总数。

格式

输入格式

输入文件只有一行，两个正整数N,M。

输出格式

输出文件只有一个正整数，表示方案总数。

样例1

样例输入1

4 3

样例输出1

13

限制

1s

提示

全部数据n<=50,m<=5

来源

OIBH
本题目由VijosCP V0.1.1 测试版 生成 请勿删除此行

分析：

设f[i]为第i个坑道使不爆炸的方案数。

当i<m时，f[i]=2*f[i-1];//因为第i个坑道只有放于不放2种情况

当i=m时，f[i]=2*f[i-1]-1;//减去的1是前m坑道都放的情况

当i>m时，f[i]=2*f[i-1]-f[i-m-1];//这是最难理解的部分，因为无论i-m-1的情况是什么，它后面都可以接i-m到m都是放的情况。或者说：当到第I个坑时，则第一个开始连着的坑其实是I-M+1，但是由于f[I-m]包括了第I-m个坑是“填”的情况，而这种情况下，已经出现了M+1个坑是连着“填”的情况，根据最优子结构，这种情况已经排除，因此我们只需要减去I-m个坑是“不填的情况”即f[I-m-1]

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 int n,m;

 long long f[];

 int main(){

     scanf("%d%d",&n,&m);

     f[]=;

     for(int i=;i<=n;i++){

         if(i==m)f[i]=f[i-]*-;

         if(i<m)f[i]=f[i-]*;

         if(i>m)f[i]=*f[i-]-f[i-m-];

     }

     printf("%lld\n",f[n]);

     return ;

 }