首页 > 代码库 > codeforces431C - k-Tree DP

codeforces431C - k-Tree DP

题意:给你一个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: darkdream10 // 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 long33 using namespace std;34 LL dp[104][104]; 35 LL dpa[104][104];36 #define md 100000000737 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\n",ans%md);74 return 0;75 }
View Code