首页 > 其他 > 详细

核电站问题

时间:2016-10-03 17:00:12      阅读:140      评论:0      收藏:0      [点我收藏+]

【题目描述】

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

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

【输入描述】

输入两个正整数N、M(1 < N < 50,2 ≤ M ≤ 5)。

【输出描述】

输出一个正整数,表示方案总数。

【样例输入】

4 3

【样例输出】

13

源代码:

#include<cstdio>
long long ans,f[50][5];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    f[1][0]=f[1][1]=1;
    for (int a=2;a<=n;a++)
    {
        for (int b=0;b<m;b++)
          f[a][0]+=f[a-1][b];
        for (int b=1;b<m;b++)
          f[a][b]=f[a-1][b-1];
    }
    for (int a=0;a<m;a++)
      ans+=f[n][a];
    printf("%lld",ans);
    return 0;
}

/*
    设f[i][j]表示到第i个坑有长度为j的连续核物质,则有如下状态转移方程:
        f[i][j]=f[i-1][j-1](j>0)
               =∑f[i-1][k](0<=k<m,j=0)。
*/

核电站问题

原文:http://www.cnblogs.com/Ackermann/p/5929212.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!