首页 > 代码库 > 核电站

核电站

描述

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

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

                                           --by NOI.openjudge

http://noi.openjudge.cn/ch0206/9267/

《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《

老题了吧。。。

好吧,是之前做的题,最近被别人提起,便整理的一下思路;

有两个思路:

1.f[n]=f[n-1]+f[n-2]+...+f[n-m];

当n不放时,前n的方案等于前n-1的方案;然后当n放的时候,可以n-1不放,等于n-2的方案数;然后当n,n-1放的时候,可以n-2不放,等于n-3的方案数......直到当n到n-m+2放的时候,可以n-m+1不放,等于n-m的方案数;

2.f[n]=2*f[n-1]-f[n-m-1];

前n的方案等于前n-1的方案乘n的情况,但这时有连续n-m+1~n全放但n-m不放的非法情况(但没有连续n-m+1~n全放且n-m也放的非法情况),她的个数为n-m-1的方案数乘1,把她减掉;

 

值得一提的是:

f[n]=f[n-1]+f[n-2]+...+f[n-m];

f[n-1]=f[n-2]+f[n-3]+...+f[n-m-1];

故f[n]=f[n-1]+f[n-1]-f[n-m-1];

即方程二可以看做方程一的优化!!!

代码如下:

#include<cstdio>using namespace std;long long f[51];int main(){    int i,k,n,m;    long long j;    scanf("%d%d",&n,&m);    f[0]=1;    for(i=1;i<=n;i++)    {        if(i-m-1<-1) j=0;        else if(i-m-1==-1)j=f[0];              else j=f[i-m-1];        f[i]=2*f[i-1]-j;    }    printf("%lld",f[n]);    return 0;}

祝AC;

 

核电站