爱华网核电站问题
TimeLimit:1000MS MemoryLimit:65536KDescription
一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。
任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数
Input
输入文件只一行，两个正整数N，M(1＜N＜50，2≤M≤5)
Output
输出文件只有一个正整数S，表示方案总数。
SampleInput
4 3
SampleOutput
13
--------------------------------------------------------------------------------------
分析：
这一题用递推，设N个坑不会发生爆炸的组合数为f(n)，每一个坑只存在放与不放两种状态，那么在i-1个坑中的左边再加1个坑且不考虑是否爆炸的方案数就是f[i]=2*f[n-1]，我们还需要再减去爆炸的方案数：当第i个坑的右边有连续m-1个坑时，这个坑就不能再放核物质，因为前m个已经确定，那么我们就要减去这种情况，此情况总数为f[n-1-m]，因此f[i]=2*f[i-1]-f[n-1-m]。
程序：
#include <iostream>
using namespace std;
unsigned long long f[60];
int main()
{
int i,n,m;
cin>>n>>m;
f[4]=f[5]=1;
for (i=6;i<n+6;i++)
f[i]=2*f[i-1]-f[i-1-m]; //递推公式
cout<<f[n+5]<<endl;
return 0;
}
P.S.
下面的是我刚才在网上看到的，感觉写的不错，贴了上来，版权归作者所有！
【算法分析】
本题是典型的组合计数问题，且数据量较大，所以应使用组合数学的算法实现。
运用升格思想，设N个坑不会发生爆炸的组合数为F(n)。假设已知F(n)以前的放置方案，在n-1个坑的左边再加一个坑得n个坑。则第n个坑的放置方案有以下情况：（为便于叙述，我们把放入核物质称为1，未放入称为0，则n个坑的状态表示为二进制数）
1、当该坑右边已有连续m-1个核物质时（即形如111…1110*），则该坑只能不放核物质，否则将发生爆炸。因为前m个状态已确定，此种情况总数为F(n-1-m)
2、对于剩下的情况，新加入的第n个坑可以为1，也可为0。此种情况总数为2*[F(n-1)-F(n-1-m)]。
通过加法原理，易得F(n)的递推关系式：
f(n)=2*f(n-1)-f(n-1-m)
f(-5)=f(-4)=f(-3)=f(-2)=0, f(-1)=f(0)=1
【程序实现的技巧】
递推关系式建立了，编程实现就没什么困难了，但还应注一下问题的规模。本题N的规模可达50，根据不等式F(50)<=250≈1015，已超过长整型的范围。但如果使用高精度计算势必会加大编程复杂度。事实上1015并不是非常大，选用合适的数据结构完全可以避免高精度运算。TurboPascal支持一种称为Extended的实型数组，它可支持最多20位的有效数字。完全可以适应本题的要求。如此一来，程序就只有短短的四行了，源程序见附录。
【进一步的优化】
首先是空间上，以上算法虽然可行，但不难发现当前状态的值只与前面有限的几项有关系，如果我们将其全部储存必然会造成空间上巨大的浪费。一种常见的做法是在数组中只保存前N项关联的数据，算完一个阶段后再刷新，将所有数据向上一阶段复制，遗弃最前面的那个阶段，继续算下一阶段。这种方法虽然可行，但数据的复制要耗费额外的时间，并且当相关的阶段较多时对原来程序要做的改动较大，既不方便又易出错。下面介绍一个本人自己在编程时摸索出来的方法，实现起来非常简单，同时也省去了复制数据的时间。设当前阶段与前M阶段相关，建立数组F[0..M]，数组存储内容与原来一样，不过访问数组下标I时，使用F[I Mod(N+1)]代替。这样只需作很小的改动，就可获得大量空间，并且Pascal处理Mod的速度是很快的，这种方法几乎没有额外的时间消耗。
在时间效率上，本算法也有可优化的地方。题目只要我们求出N规模的解，而我们通过递推关系式，把1-N规模的解都求出来了，这无疑是一个浪费。尤其是当问题规模进一步增大时，往往考虑使用母函数将问题的递推关系转化为关于N的函数直接求解。限于篇幅这里就不介绍了。总之，程序=算法+数据结构，程序的优化是无止境的，我们在平常的编程中要注重这方面的训练，才能从中获益。
