- Problem:H
- Time Limit:1000ms
- Memory Limit:65535K
Description
从前有一个绿巨人，他有个习惯是每餐只吃n个绿苹果。他有一棵神树，无限大，每一层都有且仅有k个枝杈，这k个枝杈上正好分别有1,2,3...,k个苹果。为了锻炼身体，他在同一层仅仅能选择吃完一个枝丫上的所有苹果，至少有一个枝杈是不小于d个苹果的，请帮助他计算在满足他的条件情况下，他吃掉n个苹果有多少种方法，他从树根出发（树根为1）。方法数可能很多，最后结果对1000000007 (1e9+7)取余。
Input
第一行输入有三个数字用空隔隔开，n k和d（取值范围：1≤n,k≤100; 1≤d≤k）
Output
输出一个数字，并对1000000007 (1e9+7)进行取余
Sample Input
4 3 2
4 5 2
3 3 2
3 3 3
Sample Output
6
7
3
1
思路
首先读题就读了好久，乍一看好像是树实则就是个无限长，宽为k的矩阵。每行都一样，依次为1、2、3……k。每行必须要选择一个数字累加，最后要达到n
加了一个很麻烦的条件：必须有一行选择过不小于d的数字，选择过之后就可以随便选了。于是考虑dp数组加一维来表示有没有达成过这个目标。
每个状态\(dp[m,f]\)，\(m\)表示已选择苹果数，\(f\)表示有没有选择过不小于d的苹果，于是可得状态方程：
\[\left\{
\begin{array}{c}
dp[m,0] = \sum_{i=1}^{d-1}dp[m-i][0]\\
dp[m,1] = \sum_{i=d}^{k}dp[n-i][0]+\sum_{i=1}^{k}dp[n-i][1]
\end{array}
\right.
\]
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7, N = 1e5;
ll dp[N][2];
int n, k, d;
ll Find(int x, bool f)
{
if(!f && x < d)
return dp[x][f] = 0;
if(dp[x][f] != -1)
return dp[x][f];
ll res = 0;
for (int i = 1; i <= k; i ++)
{
if(x - i < 0)
break;
if(i < d)
res += Find(x-i,f);
else
res += Find(x-i,1);
res = res % MOD;
}
return dp[x][f] = res % MOD;
}
int main()
{
while(cin >> n >> k >> d)
{
for (int i = 0; i <= n; i ++)
dp[i][0] = dp[i][1] = -1;
dp[0][0] = 0;
dp[0][1] = 1;
bool last = 0;
cout << Find(n,0) << endl;
}
return 0;
}