[數學遞推]NOIP模擬題：核電站問題 nucle 解題報告

【問題描述】

一個核電站有 N 個放核物質的坑，坑排列在一條直綫上。如果連續 M 個坑中放入核物質，則會發生爆炸，於是，在某些坑中可能不放核物質。

任務：對於給定的 N 和 M ，求不發生爆炸的放置核物質的方案總數。

【輸入格式】

輸入文件（nucle.in）只一行，兩個正整數 N ， M( 1<N<50 ， 2 ≤ M ≤ 5)

【輸出格式】

輸出文件 (nucle.out) 只有一個正整數 S ，表示方案總數。

【輸入輸出樣例】

輸入：

nucle.in

4 3

輸出：

nucle.out

13

【分析】

一開始我用組合數Combination寫的這個題，用了下面的公式：

  但是這種算法只能過3組測試數據，因為在判斷是否爆炸的問題上比較困難。

後來，我發現，這個題可以用 數值遞推來寫。

我們以N=6,M=4來舉例：
     在已經確定了前5個坑的情況下，如果再加上一個坑，只存在“放”與“不放”兩種方案，所以總數應為2*F[i-1]種。但是，如果有4個核物質放在一起，就會爆炸，那麼這種情況的實現條件就是i-M+1到i-1都放上了核物質，如果第i個坑再放，就會發生爆炸。所以，i-M+1到i-1都放上了核物質的方案總數就是它前面的方案數，即F[i-1-M]。

所以：F[i]=2*F[i-1]-F[i-1M]。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
long long F[100];
int main()
{
    freopen("nucle.in","r",stdin);
    freopen("nucle.out","w",stdout);
   
    int N,M;
    scanf("%d %d\n",&N,&M);
   
    F[4]=1;
    F[5]=1;
   
    for (int i=6;i<=N+6;i++)
    {
        F[i]=2*F[i-1]-F[i-1-M];
    }
    cout<<F[N+5]<<endl;
    return 0;
}