核电站问题 | FFY's Blog

题意

一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质.现在，请你计算：对于给定的N和M，求不发生爆炸的放置核物质的方案总数。

题解

很简单的一道DP,我们定义$F[i][j]$表示第$i$个坑已经连续装了$j$个核物质,那么状态无外乎两种:

1. 下一个坑继续装
2. 下一个坑不装

答案就是$\sum_{i=0}^mF[n][i]$

• 当连续放$m$个坑的时候,就会发生爆炸,所以$m$应该减一
• 初始条件是$F[0][0]=1$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=110;
int n,m;
ll f[maxn][10];
int main()
{
    scanf("%d%d",&n,&m);
    f[0][0]=1;m--;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        f[i][0]+=f[i-1][j];
        for(int j=1;j<=m;j++)
        f[i][j]+=f[i-1][j-1];
    }
    ll ans=0;
    for(int i=0;i<=m;i++)ans+=f[n][i];
    printf("%lld\n",ans);
    return 0;
}