选课
选课这一题我们很容易发现没有根节点，因为可能不止一个不用前置课程的节点，然后我们因为多个课程可能有一个相同的前置课程，所以我们其一可以通过森林转二叉树进行就是左孩子右兄弟，或者采用背包型树形DP，把每一次树形DP的结果都做一个背包，这样子用![f[x][t]](https://blog.hz2016.cn/wp-content/ql-cache/quicklatex.com-fefb12968e5abccb9b3b062bca01f39a_l3.png "Rendered by QuickLaTeX.com")
代表以
为跟的子树选
个节点的最大值，然后再回溯时背包一下，就可以用不同的取得不同结果，然后就可以正常动归了！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<map> #include<set> #include<queue> #include<cmath> #include<cctype> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define qread(x) x=read() #define mes(x,y) memset(x,y,sizeof(x)) #define mpy(x,y) memcpy(x,y,sizeof(x)) #define Maxn 200 #define Maxm 150 #define INF 2147483647 inline int read(){ int f=1,x=0;char ch; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } struct Edge{ int x,y,next; }a[Maxn+1];int len,first[Maxn+1]; void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=first[x];first[x]=len; } int m,f[Maxn+1][Maxm+2],h[Maxn+1]; void Dp(int x){ f[x][0]=0; for(int k=first[x];k>0;k=a[k].next){ int y=a[k].y; Dp(y); for(int t=m;t>=0;t--){ for(int j=t;j>=0;j--){ if(t-j>=0){ f[x][t]=std::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]+h[x]; } } } int n,x; int main(){ //freopen("hz2016oj-43.in","r",stdin); //freopen("hz2016oj-43.out","w",stdout); qread(n),qread(m); len=0;mes(first,0); h[0]=0; for(int i=1;i<=n;i++){ qread(x),qread(h[i]); ins(x,i); } Dp(0); printf("%d\n",f[0][m]); } |