286选课

题目简述

n个点选m个，求最大权值
要求： x选了，fa[x]也必须选

dp常规写法：(dp[i][j]表示i的子树选j个)

for(int i=m;i>=0;i--)
    for(int j=1;j<=i;j++)
        f[x][i]=max(f[x][i],f[x][i-j]+f[v][j] );
//v是x的孩纸
for(int i=m;i;i--)
    f[x][i]=f[x][i-1]+w[x];

此时时间复杂度O(nm^2)

一种神奇的优化

对树进行后序遍历
令l[x]=dfn[x]-size[x];
即l[x]表示在i节点的子树之前遍历的最后一个dfs序
(可以自己看一下dfn[x]-size[x]得到的dfn是哪个节点)

f[i][j] 表示前i个遍历的节点代价为j的最大值

f[i][j]=max(f[l[x]][j] (当前节点不选，则子树都不能选),f[i-1][j-1]+w[x] (选当前节点)) 注：x=dfn[i];

时间复杂度

O(nm)的优秀复杂度

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int ans=0;
    char c=getchar();
    while(c<'0'||c>'9')
    c=getchar();
    while(c>='0'&&c<='9')
    {
        ans=(ans<<1)+(ans<<3)+c-'0';
        c=getchar();
     } 
     return ans;
}
const int N=305; 
int n,m,cnt,num,last;
int head[N],to[N],nex[N],w[N];
int f[N][N],sz[N],dfn[N];
void add(int x,int y)
{
    cnt++;
    nex[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
void dfs(int x)//后序遍历
{
    sz[x]=1;
    for(int i=head[x];i;i=nex[i])
    {
        dfs(to[i]);
        sz[x]+=sz[to[i]];
    }
    dfn[++num]=x;
} 
int main()
{
    n=read(),m=read()+1;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        w[i]=read();
        add(x,i);
    }
    dfs(0);
    for(int i=1;i<=n+1;i++)//i是遍历顺序
        for(int j=min(m,i);j>=1;j--)
            f[i][j]=max(f[i-sz[dfn[i]]][j],f[i-1][j-1]+w[dfn[i]]);  
    printf("%d",f[n+1][m]);//n+1因为有0号节点，之前m也有+1的；
    return 0;
}