2807 - 选课
大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。
每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。下面举例说明
<table class="MsoNormalTable" border="1" cellspacing="0" cellpadding="0" style="border:none;">
<tbody>
<tr>
<td width="74" valign="top" style="border:solid black 1.5pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span> </span><span style="font-family:宋体;">课号</span><span> </span>
</p>
</td>
<td width="65" valign="top" style="border:solid black 1.5pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span style="font-family:宋体;">先修课号</span><span></span>
</p>
</td>
<td width="77" valign="top" style="border:solid black 1.5pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span style="font-family:宋体;">学分</span><span></span>
</p>
</td>
</tr>
<tr>
<td width="74" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>1</span>
</p>
</td>
<td width="65" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span style="font-family:宋体;">无</span><b><span></span></b>
</p>
</td>
<td width="77" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>1</span>
</p>
</td>
</tr>
<tr>
<td width="74" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>2</span>
</p>
</td>
<td width="65" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>1</span>
</p>
</td>
<td width="77" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>1</span>
</p>
</td>
</tr>
<tr>
<td width="74" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>3</span>
</p>
</td>
<td width="65" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>2</span>
</p>
</td>
<td width="77" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>3</span>
</p>
</td>
</tr>
<tr>
<td width="74" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>4</span>
</p>
</td>
<td width="65" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span style="font-family:宋体;">无</span><b><span></span></b>
</p>
</td>
<td width="77" valign="top" style="border:solid black 1.0pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>3</span>
</p>
</td>
</tr>
<tr>
<td width="74" valign="top" style="border:solid black 1.5pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>5</span>
</p>
</td>
<td width="65" valign="top" style="border:solid black 1.5pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>2</span>
</p>
</td>
<td width="77" valign="top" style="border:solid black 1.5pt;">
<p class="MsoNormal" align="center" style="text-align:center;">
<span>4</span>
</p>
</td>
</tr>
</tbody>
</table>
上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。
学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
<br />
Input
输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。
以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。
Output
输出文件第一行只有一个数，即实际所选课程的学分总数。
Examples
Input
7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2
Output
13
Solution C++
//此题是一个典型的树归，因为可能多门课程共用同一个先决课程，所以这是一颗普通树 //同时有些科目可能没有先决课程，这样就可能是一个森林，一个森林是没法用树归的， //那我们可以让不同的子树以0为根节点，形成一颗树，其中0为虚根，其学分为零，这样 //这样我可以枚举以0点为根的子树，选n门课时的最大值，但是这样做需要枚举根的每一个 //儿子，而且不同根，它的儿子树也不相同，所以做起来比较复杂，我们在学习树形结构时 //掌握了普通树转二叉树的方法，原则是左儿子保留不变，兄弟变右儿子，这样转了后我们 //设f[i][j]表示以i节点为根，选j门课程的最大学分，那么，对i的左儿子来说i是必选课程， //而右儿子是i的兄弟，没有必选的关系，所以选择根i节点的话，那么可以对左子树选k门 //右儿子选j-k-1门，要么就是只选右子树。 //f[i][j]=max{f[i_right][j],f[i_left][k]+f[i_right][j-k-1]+a[i]} #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1001; struct tre { int lc,rc; }; int m,n,f[maxn][maxn]={0},a[maxn]; tre tree[maxn]; void init(); int my_max(int,int); void insert(int,int); int dp(int,int); int main() { init(); cout<<dp(tree[0].lc,n)<<endl;//根0为虚根，所以其没有右子树，结果从其左子树找n门课程 return 0; } void init() { memset(tree,0,sizeof(tree)); cin>>m>>n; for(int i=1;i<=m;i++) { int fa;//fa为i的直接必选课程 cin>>fa>>a[i]; insert(i,fa);//建树 } } void insert(int son,int father) { if(!tree[father].lc)//如果父亲节点没有左儿子则，该点为其左儿子 { tree[father].lc=son; } else//如果有左儿子，则成为相邻兄弟的右儿子 { int t=tree[father].lc; while(tree[t].rc) t=tree[t].rc;//递归找到第一个没有右儿子的节点 tree[t].rc=son; } } int dp(int x,int y) { if(f[x][y]>0)return f[x][y];//如果有值则返回 if(x==0||y==0)//x==0表明该节点没有子树，y为0表明不选任何课程 { f[x][y]=0; return f[x][y]; } f[x][y]=dp(tree[x].rc,y);//先假设不选根x节点，则只选其右子树 for(int i=0;i<=y-1;i++)//如果选根x节点，左儿子选i个节点，i从[0,y-1] { f[x][y]=my_max(f[x][y],dp(tree[x].lc,i)+dp(tree[x].rc,y-i-1)+a[x]); } return f[x][y]; } int my_max(int x,int y) { return x>y ? x:y; }