Codeforces Round #247 (Div. 2) C. k-Tree （dp）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int mo = 1000000000 + 7;
 8 int dp[110][110][110];
 9 
10 int main()
11 {
12     int n, k, d, i, j, l, sum, ans;
13     while(cin>>n>>k>>d)
14     {
15         memset(dp, 0, sizeof(dp));
16         for(i = 1; i <= k; i++)
17             dp[0][i][i] = 1;
18         for(i = 1; i < n; i++)
19         {
20             for(l = 1; l <= k; l++)
21                 for(sum = 1; sum <= 100; sum++)
22                 {
23                     if(dp[i-1][l][sum] == 0)
24                         continue;
25                     for(j = 1; j <= k; j++)
26                     {
27                         if(sum + j > n)
28                             break;
29                         if(j > l)
30                         {
31                             dp[i][j][sum+j] += dp[i-1][l][sum];
32                             dp[i][j][sum+j] %= mo;
33                         }
34                         else
35                         {
36                             dp[i][l][sum+j] += dp[i-1][l][sum];
37                             dp[i][l][sum+j] %= mo;
38 
39                         }
40                     }
41                 }
42         }
43             ans = 0;
44             for(j = 0; j < n; j++)
45             for(i = d; i <= 100; i++)
46                 {
47                     ans += dp[j][i][n];
48                     ans %= mo;
49                 }
50             printf("%d\n", ans);
51         }
52         return 0;
53     }