473. 核电站问题

★   输入文件：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 }