题意：给你一个K叉数，每个节点都一定有K 个子节点，且到这K个子节点的费用为1-k，问你 费用总和为n且最少需要走过一条 d-k的边的概率
解题思路：分成两个二维DP，一个表示没有走过的，一个表示走过的，即可dp求出
解题代码：
1 /************************************************************ 2 * Author : darkdream 3 * Email : darkdream1994@gmail.com 4 * Last modified : 2014-08-02 14:28 5 * Filename : 431c.cpp 6 * Description : 7 * *********************************************************/ 8 // File Name: 431c.cpp 9 // Author: darkdream 10 // Created Time: 2014年08月01日 星期五 20时22分33秒 11 12 #include<vector> 13 #include<list> 14 #include<map> 15 #include<set> 16 #include<deque> 17 #include<stack> 18 #include<bitset> 19 #include<algorithm> 20 #include<functional> 21 #include<numeric> 22 #include<utility> 23 #include<sstream> 24 #include<iostream> 25 #include<iomanip> 26 #include<cstdio> 27 #include<cmath> 28 #include<cstdlib> 29 #include<cstring> 30 #include<ctime> 31 32 #define LL long long 33 using namespace std; 34 LL dp[104][104]; 35 LL dpa[104][104]; 36 #define md 1000000007 37 int main(){ 38 int n , k , d; 39 scanf("%d %d %d",&n,&k,&d); 40 memset(dp,0,sizeof(dp)); 41 memset(dpa,0,sizeof(dpa)); 42 dp[0][0] = 1; 43 LL ans = 0 ; 44 for(int i = 1;i <= n;i ++) 45 { 46 for(int j = i-1;j <= n;j ++) 47 { 48 if(dp[i-1][j]) 49 { 50 for(int s = 1;s <= k ; s ++) 51 { 52 if(j + s > n) 53 break; 54 if(s < d ) 55 dp[i][j+s] = (dp[i][j+s] + dp[i-1][j]) % md; 56 else 57 dpa[i][j+s] = (dpa[i][j+s] + dp[i-1][j]) % md; 58 } 59 } 60 if(dpa[i-1][j]) 61 { 62 for(int s = 1; s <= k; s++) 63 { 64 if(j + s > n) 65 break; 66 dpa[i][j+s] = (dpa[i-1][j]+ dpa[i][j+s]) %md; 67 } 68 } 69 } 70 } 71 for(int i = 1;i <= n;i ++) 72 ans =( dpa[i][n]+ ans)%md; 73 printf("%I64d ",ans%md); 74 return 0; 75 }