DP + 前缀和优化 + 组合计数问题
题目大意是一共要求携带$n$头牛,牛分为两种:1
和0
两种种类。
题目要求1
与1
之间至少要间隔$K$个0
求出满足上述要求的方案数
闫氏DP分析法:
f[i]
集合:考虑前i
头牛,且第i
头牛是1
的方案
f[i]
属性:方案数
状态计算:f[i] = f[i - k - 1] + f[i - k - 2] + ··· + f[0]
(↑集合划分的依据是题目的要求,即当前1
与上一个1
之间至少要间隔k
个0)
此处设置一个边界f[0]
表示只有0
没有1
的边界情况
如何计算最终答案
根据上述集合的含义
我们最终的答案就是把所有的f[i]
(包括f[0]
,表示该方案全是0
,没有1
)累加起来即可。
res = f[0] + f[1] + ··· + f[n]
无论是状态计算,还是答案求和,都要用到求区间和的部分
因此本题还可以采用前缀和数组,优化掉上述的计算
#include <iostream>
using namespace std;
const int N = 1e5 + 10, mod = 5000011;
int n, k;
int f[N], s[N];
int main() {
cin >> n >> k;
f[0] = s[0] = 1;
for (int i = 1; i <= n; ++ i) {
f[i] = s[max(i - k - 1, 0)]; //0用来处理所有的负数边界
s[i] = (s[i - 1] + f[i]) % mod;
}
cout << s[n] << endl;
return 0;
}
这里是如何计算相邻两个1之间0的个数的?