P2014 选课

P2014 选课

题目链接

这道题目是一个比较简单的树形\(DP\),有限制的背包问题，转化为树上问题就是要选本节点必须选这棵子树的根节点，最大化价值。

首先，设dp[i][j]表示枚举到标号为\(i\)的子树中选了\(j\)个节点的最大价值。

预处理：dp[i][1]=val[i]，在枚举到\(i\)这棵子树中只选一个节点，所以只能选根节点。

因为用0节点作为虚根节点，使这个森林成为一棵树，所以可用的空间应该到\(k+1\)，默认根节点必须选。

    转移：
        for (int j=m+1;j>=1;j--)
        {
            for (int k=0;k<j;k++)
            dp[x][j]=max(dp[x][j],dp[ed[i].e][k]+dp[x][j-k]);
        }

\(k=0\),表示不选这棵子树的所有节点及根节点

\(k<j\),因为k!=0时默认选根节点，所以可以选的节点数目是\(k-1\)。

一种是保持原来的状态，一种是在当前子树（除根节点外）选k个节点，取\(\max\)。

因为初始化根节点必须选，所以不用特判。

说的我自己都信了。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
using namespace std;
const int N=3e2+100;
struct edge{
    int s,e,net;
}ed[N];
int n,m,tot;
int dp[N][N];
int head[N];
inline void dfs(int x)
{
    for (int i=head[x];i;i=ed[i].net)
    {
        dfs(ed[i].e);
        for (int j=m+1;j>=1;j--)
        {
            for (int k=0;k<j;k++)
            dp[x][j]=max(dp[x][j],dp[ed[i].e][k]+dp[x][j-k]);
        }
    }
    return ;
}
inline void add(int s,int e)
{
    ed[++tot]=(edge){s,e,head[s]};
    head[s]=tot;
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        int fa;
        scanf("%d%d",&fa,&dp[i][1]);
        add(fa,i);
    }
    dfs(0);
    printf("%d\n",dp[0][m+1]);
    return 0;
}

P2014 选课

原文：https://www.cnblogs.com/last-diary/p/11402897.html