核电站问题 | 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$

1#include<cstdio>
2#include<cstring>
3#include<algorithm>
4#define ll long long
5using namespace std;
6const int maxn=110;
7int n,m;
8ll f[maxn][10];
9int main()
10{
11    scanf("%d%d",&amp;n,&amp;m);
12    f[0][0]=1;m--;
13    for(int i=1;i<=n;i++)
14    {
15        for(int j=0;j<=m;j++)
16        f[i][0]+=f[i-1][j];
17        for(int j=1;j<=m;j++)
18        f[i][j]+=f[i-1][j-1];
19    }
20    ll ans=0;
21    for(int i=0;i<=m;i++)ans+=f[n][i];
22    printf("%lld\n",ans);
23    return 0;
24}