首页 > 代码库 > Vijos 1232 核电站问题

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]

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int n,m; 6 long long f[100]; 7 int main(){ 8     scanf("%d%d",&n,&m); 9     f[0]=1;10     for(int i=1;i<=n;i++){11         if(i==m)f[i]=f[i-1]*2-1;12         if(i<m)f[i]=f[i-1]*2;13         if(i>m)f[i]=2*f[i-1]-f[i-m-1];14     }15     printf("%lld\n",f[n]);16     return 0;17 }

 

 

Vijos 1232 核电站问题