[USACO2.3] Cow Pedigrees [DP/二叉树]

Author Avatar
空気浮遊 2018年09月03日
  • 在其它设备中阅读本文章
  • dp
  • 二叉树
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

好难啊 QAQ

Problem

给定一个确定的深度 k 和点数 n
问有多少个不同的二叉树(左子树和右子树其中一个不同即该方案不同,每个结点度数必须为 0 或 2)

Solution

一开始考虑拉一条链下来
然后进行大讨论
然后搞了三个函数互相调用
错了之后发现可以删掉一个函数
然后发现变成了下面这样:

$f_{i,j}$ 深度一定为 $i$,结点数为 $j$ 的方案数

$S_{i,j}$ 深度 $\leq i$,结点数为 $j$ 的方案数

显然有:$S_{i,j}=\sum_{x=1}^i f_{x,j}$

由此对子树进行讨论,令其中一个子树深度达到 i - 1 即可。由于可以交换左右子树,因此方案数 *2。

那么问题来了,如果左右子树完全相同,方案数不能重复统计。

那么考虑如果左子树深度计算为 i -1,右子树深度计算同样为 i -1,此时交换左右子树会导致方案重复统计(考虑你枚举点数的循环,你已经计算过了交换左右子树的情况,或者你压根不会计算(完全二叉树))。

因此此时就不用交换左右子树了。

所以有:$$f_{i,j}=\sum_{y=1}^{j-2} f_{i-1,j-1-y}*(f_{i-1,y}+2*S_{i-2,y})$$

初始化:$f_{1,1}=1$。

Code

#include<bits/stdc++.h>
#define MOD (9901)
using namespace std;

const int N=202;
int f[N][N], f3[N][N];
int dp(int, int);
int S(int, int);
int dp(int x, int y) {
    if(x==1) return y==1;
    if(y<x) return 0;
    if(f[x][y]!=-1) return f[x][y];
    f[x][y]=0;
    for(int i=1;i<y-1;i++)
        f[x][y]=(f[x][y]+dp(x-1, y-i-1)*(S(x-2, i)*2+dp(x-1, i)))%MOD;
    return f[x][y];
}
int S(int x, int y) {
    if(x<=0) return 0;
    if(f3[x][y]!=-1) return f3[x][y];
    f3[x][y]=0;
    for(int i=1;i<=x;i++) f3[x][y]=(f3[x][y]+dp(i, y))%MOD;
    return f3[x][y];
}

int main() {
    freopen("nocows.in","r",stdin);
    freopen("nocows.out","w",stdout);
    ios::sync_with_stdio(false), cin.tie(0);
    int n, k;
    cin>>n>>k;
    memset(f, -1, sizeof(f)), memset(f3, -1, sizeof(f3));
    cout<<dp(k, n)<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-usaco-nocows.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

    aoweiyin
    aoweiyin  2018-09-04, 15:10

    此题让我突然想起了[SHOI2012]随机树,QwQ

    • 在新标签页中打开
    • 分享到 Twitter
      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • May 2025 1
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 31
    • August 2018 18
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 281
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material