题意：一共有N只牡牛（公牛）和牝牛（母牛），每2只牡牛间至少要有K只牝牛才不会斗殴。问无斗殴发生的方案数。
解法：f[i][j]表示一共i只牛，最后一只是j（0为牝牛，1为牡牛）的方案数。
f[i][0]=f[i-1][1]+f[i-1][0]; f[i][1]=f[i-k-1][1]+f[i-k-1][0](这个小心不要漏了，因为没有要求2只牡牛间一定是K只牝牛);
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6 #define N 100010
7 #define mod 5000011
8
9 int f[N][2];
10 int main()
11 {
12 int n,k;
13 scanf("%d%d",&n,&k);
14 f[1][0]=f[1][1]=1;
15 for (int i=2;i<=n;i++)
16 {
17 f[i][0]=(f[i-1][0]+f[i-1][1])%mod;
18 f[i][1]=(i>k+1)?f[i-k-1][0]+f[i-k-1][1]:1;
19 }
20 printf("%d\n",(f[n][0]+f[n][1])%mod);
21 return 0;
22 }
1
优化：可发现每次调用状态都是[0]和[1]一起，所以可以简化成一维。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6 #define N 100010
7 #define mod 5000011
8
9 int f[N];
10 int main()
11 {
12 int n,k;
13 scanf("%d%d",&n,&k);
14 f[1]=2;
15 for (int i=2;i<=n;i++)
16 f[i]=(f[i-1]+((i>k+1)?f[i-k-1]:1))%mod;
17 printf("%d\n",f[n]);
18 return 0;
19 }
2