选课
选课这一题我们很容易发现没有根节点,因为可能不止一个不用前置课程的节点,然后我们因为多个课程可能有一个相同的前置课程,所以我们其一可以通过森林转二叉树进行就是左孩子右兄弟
,或者采用背包型树形DP,把每一次树形DP的结果都做一个背包,这样子用代表以
为跟的子树选
个节点的最大值,然后再回溯时背包一下,就可以用不同的
取得不同
结果,然后就可以正常动归了!
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]); } |