luogu2014选课(树形dp)

动态规划——树形dp
题目传送门

方法

• 先摆出状态再看怎么来的
  设dp[i][j]表示以i为根的子树选了j门课的最大点权和(学分)
• 因为选了儿子必须选爸爸，那么儿子的状态确定后(最大学分)，爸爸转移的一种方式就确定了
• 那我们考虑转移(父节点:now，儿子节点:qw)
  先看转移再解释：(j,k为枚举的选的课的数量)(暂时没有算上选now的值)
  dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[qw][k])
• 显然，我如果在之前的儿子上转移出来了dp[now][j-k]，那么和dp[qw][k]拼起来就是想要的状态了，但是注意一点：我们只是还没有把now的权值加进去，但是我们要假设它加进去了，以便转移，转移完之后再统一加上：dp[now][j]+=v[now](枚举j)

Code

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 350
using namespace std;
const int Inf=1e9;
il int read()
{
    rg int s=0,m=0;rg char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
int n,m;
int fa[N],v[N];
int hd[N],cnt;
int dp[N][N];
struct EDGE{int to,nxt;}ljl[N<<1];
il void add(rg int p,rg int q){ljl[++cnt]=(EDGE){q,hd[p]},hd[p]=cnt;}
void dfs(rg int now)
{
    for(rg int i=hd[now];i;i=ljl[i].nxt)
    {
        rg int qw=ljl[i].to;
        dfs(qw);
        for(rg int j=m;j>=1;--j)
            for(rg int k=j-1;k>=0;--k)
                dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[qw][k]);
    }
    for(rg int j=1;j<=m;++j)
        dp[now][j]+=v[now];
}
int main()
{
    n=read(),m=read();m++;
    for(rg int i=1;i<=n;++i)
    {
        fa[i]=read(),v[i]=read();
        add(fa[i],i);
    }
    dfs(0);
    printf("%d\n",dp[0][m]);
    return 0;
}