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;
}
很有用的一种优化,如果我没记错的话,洛谷上有一个苹果树的树形DP就是利用了后序遍历进行了优化
秀,tql
秀,太优秀了,Orz,膜拜大佬