【DP】选课 背包类树形dp

• f[0][m]可知f[i][j]是以i为根节点的子树有的值，其中不包括i
• 背包问题倒着循环--
• 注意vector的使用 son[fa].push_back(i)即输入 son[x].size长度查询

遗留问题：

1.  ·背包为什么倒着循环
2. ·本题中f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);是否会重复计算
3. ·tj循环能不能放在大括号外

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>son[500];
int f[500][500],s[310],n,m;
void dp(int x) {
f[x][0]=0;
for(int i=0;i<son[x].size();i++) {
int y=son[x][i];
dp(y);
for(int t=m;t>=0;t--)
for(int j=t;j>=0;j--)
f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);
}
if(x!=0)
for(int t=m;t>0;t--)
f[x][t]=f[x][t-1]+s[x];
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
int fa;
scanf("%d%d",&fa,&s[i]);
son[fa].push_back(i);
}
memset(f,0xcf,sizeof(f));
dp(0);
cout<<f[0][m]<<endl;
return 0;
} 

最后

以上就是合适飞机为你收集整理的【DP】选课 背包类树形dp的全部内容，希望文章能够帮你解决【DP】选课 背包类树形dp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。