题解：SP14871 AU7_5 - STUDENTS
zhangyizexiaozhi
·
·
题解
题目传送门。
博客食用。
题目大意
有 n 个位置排成一排，每个位置可以安排一名男生或一名女生。要求任意两名男生之间至少间隔 k 个女生。求合法的安排方案数，结果对 5000011 取模。
思路分析
这道题是组合数学，可以用动态规划做。
dp 初始化
- 初始化为零，用于计算合法序列的数量。
-
memset(dp,0,sizeof(dp));
dp[0]=1;
dp 的含义
## dp 的动态转移方程
1. 第 $i$ 个位置放女生，那么前 $i-1$ 位只要构成合法序列即可，那么方案数就是 $\text{dp}[i-1]$。
2. 第 $i$ 个位置放男生，那么前一个男生必须至少在位置 $i-(k+1)$ 或更之前，意味着位置 $[i-k, i-1]$ 这 $k$ 个位置必须全是女生，因此，方案数取决于前 $i-(k+1)$ 个位置的合法序列数，即加上 $\text{dp}[i-k-1]$。
3. 第 $i$ 个位置放男生并且是边界情况 $(i\leq k)$，前面所有位置必须全是女生才可以，即是第一个男生，加 $1$ 代表前面全部填女生的那一种特定情况。
综上得出动态转移方程如下：
$$
\text{dp}[i] = \begin{cases}
\text{dp}[i-1]
\\ \text{dp}[i]+\text{dp}[i-k-1] & i>k
\\ \text{dp}[i]+1 & i \leq k
\end{cases}
$$
```cpp
dp[i]=dp[i-1];
if(i-k-1>=0){
dp[i]=(dp[i]+dp[i-k-1])%5000011;
}
else{
dp[i]=(dp[i]+1)%5000011;
}
```
## dp 的输出
输出长度为 $n$ 的合法序列总数。
```cpp
cout<<dp[n]<<endl;
```
# 代码实现
```
#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int main(){
int c,n,k;
cin>>c;
while(c--){
cin>>n>>k;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;i++){
dp[i]=dp[i-1];//第i位放女生
if(i-k-1>=0){
dp[i]=(dp[i]+dp[i-k-1])%5000011;//第i位放男生
}
else{
dp[i]=(dp[i]+1)%5000011;//第i位放男生且前面不足k个位置
}
}
cout<<dp[n]<<endl;
}
return 0;
}
```