AcWing 1307. 牡牛和牝牛

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1307. 牡牛和牝牛原题链接简单

作者：

王雨阳 , 2020-03-23 20:08:40 , 所有人可见 , 阅读 3678

57

9

Description:

约翰要带 N 只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛。

牛们要站成一排，但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有 K 只牝牛。

请计算一共有多少种排队的方法，所有牡牛可以看成是相同的，所有牝牛也一样，答案对 5000011 取模。

Solution:

设 $f[i]$ 表示 i 头牛站成一排有多少种排队的方法。

显然，对于$1 \leq i \leq k + 1, f[i] = i + 1$
因为这些情况最多有一只牡牛。

假设有i头牛排队，我们考虑最后一头牛，是牡牛或者不是牡牛。

如果不是牡牛，那么前i-1头牛任意排队就可以了，方案为f[i - 1]。
如果是牡牛，那么第i - k 到 i - 1都不能是牡牛，方案数为f[i - k - 1]

所以 ,f[i] = f[i - 1] + f[i - k - 1]

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int mod = 5000011, N = 1e5 +100;
int n, k, f[N];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= k + 1; i ++)  
        f[i] = i + 1;
    for(int i = k + 2; i <= n; i ++)
        f[i] = (f[i - 1] + f[i - k - 1]) % mod;
    printf("%d\n", f[n]);
    return 0;
}