洛谷2014 选课

@Llf0703  December 6, 2018

题目链接:https://www.luogu.org/problemnew/show/P2014

似乎有直接树形dp的做法,但我还是多叉转二叉做的。

我们用 $f[x][cnt]$ 表示当前x节点,在以 $x$ 为根的子树中选 $cnt$ 个节点。

对于每一个节点,可以有选和不选两个选项,如果不选就把 $cnt$ 全都给兄弟节点,也就是右节点;如果要选就把 $cnt$ 分别分配给 $x$ 的兄弟和以 $x$ 为先修的课程,也就是左节点。第二种情况需要枚举一下 $cnt$ 分配的个数。

所以我们就得到方程:

$$f[x][cnt]=max \begin{cases} f[tree[x].rs][cnt] \\ f[tree[x].rs][cnt-i-1]+f[tree[x].ls][i]+s[x] & i<cnt \end{cases}$$

然后记搜即可。

int n,m,a,b,c,s[305],f[305][305];
struct node{
    int ls,rs;
} tree[305];

inline void init()
{
    memset(f,-1,sizeof(f));
    memset(tree,-1,sizeof(tree));
}

int dfs(int x,int cnt)
{
    if (x==-1 || !cnt) return 0;
    if (f[x][cnt]!=-1) return f[x][cnt];
    int &ans=f[x][cnt];
    ans=dfs(tree[x].rs,cnt);
    for (int i=0;i<cnt;i++) ans=max(ans,dfs(tree[x].rs,cnt-i-1)+dfs(tree[x].ls,i)+s[x]);
    return ans;
}

int main()
{
    n=read(); m=read();
    init();
    for (int i=1;i<=n;i++)
    {
        a=read(); s[i]=read();
        tree[i].rs=tree[a].ls;
        tree[a].ls=i;
    }
    printf("%d",dfs(0,m+1));
    return 0;
}

添加新评论