codeforces C. k-Tree

思路：dp[i][j]表示和为i，最大值为j的方案数。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #define maxn 100010
 6 #define ll long long
 7 using namespace std;
 8 const int mod=1000000007;
 9 
10 int n,k,d;
11 ll dp[200][110];
12 
13 int main()
14 {
15     scanf("%d%d%d",&n,&k,&d);
16     for(int i=1; i<=n; i++)
17     {
18         dp[i][i]=1;
19     }
20     for(int i=1; i<=n; i++)
21     {
22         for(int j=1; j<=k; j++)
23         {
24             for(int x=1; x<=k; x++)
25             {
26                 if(j>=x)
27                 {
28                     dp[i+j][j]+=dp[i][x];
29                     dp[i+j][j]%=mod;
30                 }
31                 else
32                 {
33                     dp[i+j][x]+=dp[i][x];
34                     dp[i+j][x]%=mod;
35                 }
36             }
37         }
38     }
39     ll ans=0;
40     for(int i=d; i<=k; i++)
41     {
42         ans+=dp[n][i];
43         ans%=mod;
44     }
45     printf("%lld
",ans);
46     return 0;
47 }
View Code