模拟赛20181016 dp

给出1-n的序列插入一个bst；

给出T组询问，包含n,h分别代表点数为n,高度为h的树，求所有插入顺序的合法方案数，模1e9+7

样例输入

2 1

样例输出

#include<bits/stdc++.h>

#define LL long long

#define rep(i,x,y) for(register int i=x;i<=y;i++)

using namespace std;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}

const int N=;

const int mod=;

LL C[N][N],f[N][N],g[N];

int T;

int main(){

    freopen("bst.in","r",stdin);

    freopen("bst.out","w",stdout);

    int nn=,hh=;

    rep(i,,nn) C[i][]=;C[][]=;

    rep(i,,nn)rep(j,,i)

    C[i][j]=1LL*(C[i-][j-]+C[i-][j])%mod;

    memset(g,,sizeof g);

    memset(f,,sizeof f);

    f[][]=g[]=;

    rep(i,,hh){

        rep(j,,nn)if(f[i][j])rep(k,,nn-j-)

        f[i+][j+k+]=(f[i+][j+k+]+1LL*f[i][j]*(g[k]*+f[i][k])%mod*C[j+k][j]%mod)%mod;

        rep(j,,nn) g[j]=(g[j]+f[i][j])%mod;}

    T=read();while(T--){

        int n=read(),h=read();

        printf("%lld\n",f[h+][n]);}

    return ;}

我们考虑点数n+1，我们发现序列内部的顺序并没有什么卵用，而且树的形状发现有递归的情况

那么dp[i][j] 代表高度为i点数为j 的方案数

刷表法更加好用，所以转移方程可以转化为

dp[i+1][j+k+1]+=dp[i][j]*dp[i(0-i)][k]*C[j+k][j]

我们发现两个子树中至少有一个的高度是h，剩下一个需要利用前缀和保存以平衡复杂度

那么大力枚举高度i，并更新点j由1-n,更新答案，最终将所有点在此高度下的情况前缀和更新

完结撒花

秒客网

模拟赛20181016 dp

相关文章