dp简单计数

103 阅读 0 评论 68 点赞

我是靠谱客的博主敏感身影，这篇文章主要介绍dp简单计数，现在分享给大家，希望可以做个参考。

题目:https://codeforces.com/problemset/problem/431/C


#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
ll da[105];
ll db[105];
void solve()
{
da[0] = 1;//dynamic plan must have initial value
ll n, k, d;
scanf_s("%lld%lld%lld", &n, &k, &d);
for (int i = 1; i <= n; i++)//对应的权值
{
for (int j = 1; j <= i && j <= k; j++)
{
db[i] += db[i - j];//表示满足条件的
db[i] %= mod;
if (j >= d)
{
db[i] += da[i - j];
db[i] %= mod;
}
else
{
da[i] += da[i - j];
da[i] %= mod;
}
}
}
cout << db[n] << endl;
}
int main()
{
solve();
}