首页 > 代码库 > Codeforces Round #247 (Div. 2) C. k-Tree (dp)
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。