洛谷2014 选课

题意

要从 $N$ 门课中选出 $M$ 门，有的课有价值和先决条件，求价值总和最大值。

其中 $N,M\le 300$ 。

题解

1.多叉转二叉

我们用 $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;
}

2.直接树形dp

用 $f[x][j]$ 表示在以 $x$ 为根的子树中选 $j$ 门课的最优情况。

枚举 $x$ 的子节点 $y$ ，然后枚举以 $y$ 为根子树选的课程数 $k$ ，得到状态转移方程式：

$$f[x][j]=max(f[x][j],f[y][k]+f[x][j-k])$$

struct Edge {
    int next,to;
} edge[305];
int cnt,head[305],n,m,a,b,f[305][305],siz[305];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    siz[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        dfs(y);
        siz[x]+=siz[y];
        for (int j=min(m+1,siz[x]);j;j--)
            for (int k=min(siz[y],j-1);k>=0;k--)
                f[x][j]=max(f[x][j],f[y][k]+f[x][j-k]);
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        a=read(); f[i][1]=read();
        add(a,i);
    }
    dfs(0);
    printf("%d",f[0][m+1]);
    return 0;
}