F - k-Tree
Codeforces Round #247 (Div. 2)
Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a k-tree.
A k-tree is an infinite rooted tree where:
each vertex has exactly k children;
each edge has some weight;
if we look at the edges that goes from some vertex to its children (exactly kedges), then their weights will equal 1,?2,?3,?...,?k.
The picture below shows a part of a 3-tree.
As soon as Dima, a good friend of Lesha, found out about the tree, he immediately wondered: "How many paths of total weight n (the sum of all weights of the edges in the path) are there, starting from the root of a k-tree and also containing at least one edge of weight at least d?".Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (109?+?7).
Input
A single line contains three space-separated integers: n, k and d (1?≤?n,?k?≤?100; 1?≤?d?≤?k).
Output
Print a single integer — the answer to the problem modulo 1000000007 (109?+?7).
Example
Input
3 3 2
Output
3
Input
3 3 3
Output
1
Input
4 3 2
Output
6
Input
4 5 2
Output
7
題意：對于一個k叉樹辫诅，從根節(jié)點拘央，有多少條路徑長度為n，且路徑上的路徑最小值不小于d。k叉樹邊的權(quán)值從1到k
解法：dp算法腐螟，dp[i]為長度為i的路徑的條數(shù)睛挚，長度為i可能是長度為i-1的路徑加一徙歼，或i-2長度的路徑加2酿矢，最小可能為i-k長度加k，因為是k叉樹盔夜，最長邊長度為k负饲，所以dp[i]=dp[i-1]+dp[i-2]+......dp[i-k]堤魁，但是不能全部算上，因為這里包括所有邊長度都小于d的返十，所以要把不和條件的減去妥泉。那么dp0[i]表示最長邊不超過d的路徑的數(shù)量，那么dp0[i]=dp0[i-1]+......+dp-[i-d]洞坑，dp[n]-dp0[n]即為所求答案
代碼：
#include<iostream>
using namespace std;
long long dp[105];
long long dp1[105];
#define MOD 1000000007
int main()
{
int n,k,d;
cin>>n>>k>>d;
dp1[0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(i-j>=0){
if(j<d)
dp1[i]+=dp1[i-j];
else
dp[i]+=dp1[i-j];
dp[i]+=dp[i-j];
dp[i]%=MOD;
dp1[i]%=MOD;
}
}
}
cout<<dp[n]<<endl;
}
