473. 核电站问题

2018-06-17 23:06:08来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

★   输入文件:nucle.in   输出文件:nucle.out   简单对比
时间限制:1 s   内存限制:128 MB

【问题描述】

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

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

【输入格式】 
     输入文件(nucle.in)只一行,两个正整数 N , M( 1<N<50 , 2 ≤ M ≤ 5)

【输出格式】 
     输出文件 (nucle.out) 只有一个正整数 S ,表示方案总数。

【输入输出样例】
 
输入:

nucle.in

4 3

输出:

nucle.out

13

 

思路:

若用f[i]储存在这个坑时的已经计算过的所有情况

对于一个坑,有三种情况

1:n<m在这种情况下只有两种情况

   放与不放。于是此时所有的情况就是2*f[i-1]

2:n==m

   这种情况下也可以选择放与不放,但是当放的时候,若前n-1个已经放了物质,则第n个不能放

  于是所有的情况就是2*f[i-1]-1

3:n>m

  当选择不放的时候,就是加上f[i-1]的所有情况

   当选择放的时候,要考虑若放上会爆炸的情况,我们先想若放上之后不爆炸的情况,就是f[i-1],再减去放上之后会爆炸的情况。那么放上之后会爆炸的情况是什么呢?如果我们放上会爆炸,那么i-m-1个一定没有放。所以放上会爆炸的情况就是f[i-m-1].

So这种情况下的所有情况就是2*f[i-1]-f[i-m-1]

 

 1 #include<cstdio>
 2 using namespace std;
 3 int main()
 4 {
 5     freopen("nucle.in","r",stdin);
 6     freopen("nucle.out","w",stdout);
 7     long long f[50];
 8     int i,n,m;
 9     cin>>n>>m;
10     f[0]=1;
11     for(i=1;i<=n;i++)
12     {
13      if(i<m) f[i]=2*f[i-1];
14      if(i==m) f[i]=2*f[i-1]-1;
15      if(i>m) f[i]=2*f[i-1]-f[i-m-1];
16     }
17     cout<<f[n]<<endl;
18     return 0;
19 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:stl map容器 学习

下一篇:读书笔记 effective c++ Item 32 确保public继承建立“is-a”模