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

Author Avatar
ajcxsu 2018年09月03日
  • 65 次阅读

好难啊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://acxblog.site/archives/sol-usaco-nocows.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

    aoweiyin
    aoweiyin  2018-09-04, 15:10

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