P2014 选课

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,m;
 5 struct node{
 6     int lson,rson;
 7 }a[305];
 8 bool gotson[305];
 9 int dp[305][305],s[305];
10 void DP(int rc,int rm)
11 {//if一定要打，要不然会回到虚根导致dp错误
12     if(dp[rc][rm]) return;
13     if(a[rc].rson)
14     DP(a[rc].rson,rm);
15     dp[rc][rm]=dp[a[rc].rson][rm];
16     for(int k=1;k<=rm;k++){
17         if(a[rc].lson)
18         DP(a[rc].lson,k-1);
19         if(a[rc].rson)
20         DP(a[rc].rson,rm-k);
21         dp[rc][rm]=max(dp[rc][rm],dp[a[rc].lson][k-1]+dp[a[rc].rson][rm-k]+s[rc]);
22     }
23 
24 }
25 int main(void)
26 {
27     scanf("%d%d",&n,&m);
28     for(int i=1,k;i<=n;++i)
29     {
30         scanf("%d%d",&k,s+i);
31         if(gotson[k])
32         {
33             k=a[k].lson;
34             while(a[k].rson) k=a[k].rson;//找最深的右儿子
35             a[k].rson=i;
36         }
37         else {
38             gotson[k]=1;a[k].lson=i;
39         }//多叉转二叉树
40     }
41     DP(0,m+1);
42     printf("%d",dp[0][m+1]);
43 }