hdu 4359 Easy Tree DP? 夜

http://acm.hdu.edu.cn/showproblem.php?pid=4359

上不起呀错在了细节上导致比赛时没做出了呀题不并不难

左子树的和小于右子树的和由于都是2的幂所以只要且必须右子树上有剩下数中最大的那个就可以了(当然左/右为空的特殊)

查询时注意根节点的选取是任意的所以有假如说有n个节点那根节点就有n种选法还有根节点选出后如果左右都有节点

那么剩余最大节点一定在右面

所以情况

1 左/右为空

2 左右深度同时为D-1

3 只有左/右深度为D-1

要注意时刻取模

这题会用到组合中的从几个点中选几个点的情况数量由于360太大所以轻松超long long

所以用函数求的话很难取模所以要用的递推即快右又准（比赛时就是这里错了呜呜呜`````````````）

代码及其注释：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<stack>
#include<cmath>
#define LL long long

using namespace std;

const LL MOD=1000000007;
const int N=365;
LL ans[N][N];//节点数为i 深度为j 的情况数
LL c[N][N];//从i 个节点中选取 j 个节点的情况数
LL te[N][N];// 有i 个节点 组合成的 深度从1 到 j 的情况数 只是怕有重复的情况 避免浪费时间
LL dp(int ,int );
inline LL Ftemp(int k1,int k2)
{
    if(te[k1][k2]!=-1)
    return te[k1][k2];
    te[k1][k2]=0;
    for(int l=1;l<=k1&&l<=k2;++l)
    {
        te[k1][k2]=(te[k1][k2]+dp(k1,l))%MOD;//枚举 深度 取模
    }
    return te[k1][k2];
}
LL dp(int i,int d)
{
    if(ans[i][d]!=-1)
    return ans[i][d];
    if(i<d)//特殊情况 深度不能超过节点数量
    {
        ans[i][d]=0;
        return ans[i][d];
    }
    if(i==1||d==1)//边界
    {
        if(i==1&&d==1)//若都为1 则为答案 1
        ans[i][d]=1;
        else
        ans[i][d]=0;//否则为0
        return ans[i][d];
    }
    ans[i][d]=(dp(i-1,d-1)*2)%MOD;//左/右为空的情况
    for(int j=d-1;j<i-1&&i-j-1>=d-1;++j)
    {
        ans[i][d]=(ans[i][d]+(((dp(j,d-1)*dp(i-j-1,d-1))%MOD)*c[i-2][j-1])%MOD)%MOD;//两边深度都为D-1 的情况
    }
    for(int j=d-1;j<i-1&&i-1-j>0;++j)
    {
        LL temp=Ftemp(i-1-j,d-2);//有 i-1-j 个节点  深度最大为d-2 的情况数
        ans[i][d]=(ans[i][d]+(((dp(j,d-1)*temp)%MOD)*c[i-2][j-1])%MOD)%MOD;//右边深度为D-1 左边深度小于D-1 的情况
        ans[i][d]=(ans[i][d]+(((dp(j,d-1)*temp)%MOD)*c[i-2][j])%MOD)%MOD;//左边深度为D-1 右边深度小于D-1 的情况 它们只在组合数上不同
    }
    ans[i][d]=(ans[i][d]*i)%MOD;//根节点的选取有i 种情况
    return ans[i][d];
}
void begin()
{
    for(int i=0;i<N;++i)
    c[i][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=1;j<=i;++j)
        {
            if(i==j)
            c[i][j]=1;
            else
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;//组合递推法  一定要牢记呀 吸取教训
        }
    }
}
int main()
{

    //freopen("data.txt","r",stdin);
    int T;
    begin();
    memset(ans,-1,sizeof(ans));
    memset(te,-1,sizeof(te));
    scanf("%d",&T);
    for(int cas=1;cas<=T;++cas)
    {
        int n,d;
        scanf("%d %d",&n,&d);
        printf("Case #%d: ",cas);
        cout<<dp(n,d)<<endl;
    }
    return 0;
}