题目链接：

方法：

表面上看输入是一个森林的结构，其实可以用0节点作为父节点将森林中所有的树串起来作为一个树，然后开始DP，设F（P，x)是P为根的子树上选x个能获得的最大值的集合。

 

　　　　　　{

　　　　　　{0}; x==0

F（P，x) =

　　　　　　{v+P的价值|v属于{F(s,x1)|s是p的直接子节点 && 0<=x1<min( (p为根? x+1:x),m)   }跑一个以一个s作为分组的01分组背包形成的集合};0<x<=min(((p为根? m:m-1)),  p那里最多选出多少)

　　　　　　}

 

代码：

#include 
     
      #include 
      
       #include
       
        using namespace std;int n,m;struct Staff{    int cost;    int value;};struct Adge{    int vetex;    Adge* nextAdge;};struct Node{    Adge* firstAdge;    bool isRoot;    int value;    Staff staff[201];    int StaffCount;    int maxChose;};Node nodes[201];int myMax(int x,int y){    return x>=y? x:y;}void createAdge(int father,int son){    Adge* adge = (Adge*)(malloc(sizeof(Adge)));    adge->vetex = son;    if(nodes[father].firstAdge==NULL)        adge->nextAdge = NULL;    else        adge->nextAdge = nodes[father].firstAdge;    nodes[father].firstAdge = adge;    }void DFSDP(int root){    Adge* adge = nodes[root].firstAdge;    int v,sonCount=0;    int innerDP[205];    memset(innerDP,0,sizeof(innerDP));    while(adge!=NULL)    {        v= adge->vetex;        DFSDP(v);        nodes[root].maxChose+=nodes[v].maxChose;        for(int i=m;i>=0;i--)            for(int j=1;j<=nodes[v].StaffCount;j++)                if(nodes[v].staff[j].cost<=i)                    innerDP[i] = myMax(innerDP[i-nodes[v].staff[j].cost]+nodes[v].staff[j].value,innerDP[i]);        adge=adge->nextAdge;        sonCount++;    }    if(sonCount==0)    {        nodes[root].StaffCount++;        Staff st;        st.cost=1;        st.value=nodes[root].value;        nodes[root].staff[nodes[root].StaffCount]=st;    }    else    {        int base = root==0?1:0;        for(int i=0;i
        
       
      
     

 感想：实在不知道这个报告应该怎么描述，反正就是知道