USACO Cow Pedigrees 【Dp】

朴灿烈づ我的快乐病毒、 2021-12-10 16:41 250阅读 0赞

一道经典Dp.

定义dp[i][j] 表示由i个节点,j 层高度的累计方法数

状态转移方程为: 用i个点组成深度最多为j的二叉树的方法树等于组成左子树的方法数

乘于组成右子树的方法数再累计。

  1. &
  2. / \
  3. @ #
  4. / \
  5. @ @

如图中 & 为顶点, @ 为左子树, # 为右子树

需要注意的是,左子树的节点数目同样也为奇数

然后遍历一遍从k = 1 到 i - 2, 考虑上一层所有的左/右子树方法数再作累加

最后输出答案的时候减去上一层累加数即可

  1. /*
  2. ID: wushuai2
  3. PROG: nocows
  4. LANG: C++
  5. */
  6. //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
  7. #include <stdio.h>
  8. #include <iostream>
  9. #include <fstream>
  10. #include <cstring>
  11. #include <cmath>
  12. #include <stack>
  13. #include <string>
  14. #include <map>
  15. #include <set>
  16. #include <list>
  17. #include <queue>
  18. #include <vector>
  19. #include <algorithm>
  20. #define Max(a,b) (((a) > (b)) ? (a) : (b))
  21. #define Min(a,b) (((a) < (b)) ? (a) : (b))
  22. #define Abs(x) (((x) > 0) ? (x) : (-(x)))
  23. #define MOD 1000000007
  24. #define pi acos(-1.0)
  25. #define RV(num) ((num) > 0 ? 0 : 1)
  26. using namespace std;
  27. typedef long long ll ;
  28. typedef unsigned long long ull ;
  29. typedef unsigned int uint ;
  30. typedef unsigned char uchar ;
  31. template<class T> inline void checkmin(T &a,T b){
  32. if(a>b) a=b;}
  33. template<class T> inline void checkmax(T &a,T b){
  34. if(a<b) a=b;}
  35. const double eps = 1e-7 ;
  36. const int M = 660000 ;
  37. const ll P = 10000000097ll ;
  38. const int INF = 0x3f3f3f3f ;
  39. const int MAX_N = 20 ;
  40. const int MAXSIZE = 101000000;
  41. int N, K;
  42. int dp[220][120];
  43. int main() {
  44. ofstream fout ("nocows.out");
  45. ifstream fin ("nocows.in");
  46. int i, j, k, l, m, n, t, s, c, w, q, num;
  47. fin >> N >> K;
  48. for(i = 1; i <= N; ++i)
  49. dp[1][i] = 1;
  50. for(j = 1; j <= K; ++j){
  51. for(i = 1; i <= N; ++i){
  52. if(i & 1){
  53. for(k = 1; k <= i - 2; ++k){
  54. if(k & 1){
  55. dp[i][j] = (dp[k][j - 1] * dp[i - 1 - k][j - 1] + dp[i][j]) % 9901;
  56. }
  57. }
  58. }
  59. }
  60. }
  61. fout << (dp[N][K] - dp[N][K - 1] + 9901) % 9901 << endl;
  62. fin.close();
  63. fout.close();
  64. return 0;
  65. }

转载于:https://www.cnblogs.com/wushuaiyi/p/4297008.html

发表评论

表情:
评论列表 (有 0 条评论,250人围观)

还没有评论,来说两句吧...

相关阅读

    相关 USACO10HOL】 Cow Politics

    题目大意 给出k组点,求出组内两点间的最大距离 核心思路 考虑贪心,每组内的最深一点一定是两最远距离点对之一。 证明很简单,可以分为在该点的祖先相同和祖先不同的