树形动态规划*

(1) 苹果树

【问题描述】有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）。这棵树共有 n 个结点（叶子点或者树枝分叉点），编号为1～n，树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树：

2 5

       \ /

3 4

            \ /

       1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。已知需要保留的树枝数量为 q，求出最多能留住多少苹果。

数据规模：1＜n≤100，1≤q≤n，每个树枝上的苹果数量不超过30000。

【分析】

1. 状态表示：f(i,n)表示在以 i 为根结点的二叉树中保留 n 个树枝后，留住苹果的最大值。

2. 状态转移方程：f(i,n)＝max{f(i 的左儿子, k)＋f(i 的右儿子, n－k)＋i→num}，其中num指该结点与父亲结点连接成的树枝上的苹果数，0≤k≤j

3. 实现：由于要把儿子的信息传递给父亲，所以用后序遍历（下面的代码是后序遍历，虽然看起来不像）。

struct node

{

int num;      // 指该结点与父亲结点连接成的树枝上的苹果数  node *leftchild, *rightchild;

} mem[N]; int postorder(node *i, int a) {  if (i==NULL) return 0;  int result=0;  for (int k=0; k<=a; k++)   result = max(result,     postorder(i->leftchild, k) + postorder(i->rightchild, a-k) + i->num);  return result; }

(2) 选课

【问题简述】某大学有 m 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课，那么只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择 n 门课程学习，他能获得的最大学分是多少？

【输入格式】第一行有两个整数 m，n 用空格隔开。(1≤n≤m≤1000)

接下来的 m 行：第 I＋1行包含两个整数 ki 和 si，ki 表示第 I 门课的直接先修课，si 表示第 I 门课的学分。

若 ki＝0表示没有直接先修课（1≤ki≤m，1≤si≤10）。

【输出格式】只有一个数，是选 n 门课程的最大得分。

【分析】

1. 状态表示：f(i,c)表示在以 i 为根结点的二叉树中取 c 门课程后得到的学分的最大值。

2. 状态转移方程：

f(i,c)＝max{f(i->leftchild, k－1)＋i->v＋f(i->rightchild, c－k)}，0≤k≤j

3. 实现：

Ÿ 把0作为顶点。

Ÿ 需要把多叉树转化为二叉树（左儿子右兄弟）。

Ÿ 后序遍历

#include <iostream> #include <cstring> using namespace std; // -1表示没有结点。 struct node {  int value, leftchild, rightchild; } a[1002]; int F[1002][152], parent[1002]; int m,n; #define f(x,y) F[(x)+1][(y)+1] int postorder(int x, int y) {  if (f(x,y)>=0) return f(x,y);  int m=postorder(a[x].rightchild, y);					// 只有右子树的情况
for (int k=1; k<=y; k++)   m = max(m, postorder(a[x].leftchild,k-1) + a[x].value +       postorder(a[x].rightchild,y-k));  return f(x,y)=m; }  int main() {  cin>>m>>n;  memset(F,0,sizeof(F));  memset(parent,0,sizeof(parent));  memset(a,-1,sizeof(a)); // 树变二叉树 int k,s;  for (int i=1; i<=m; i++) {   cin>>k>>s;   a.value=s;   if (parent[k]==0)    a[k].leftchild=i;   else    a[parent[k]].rightchild=i;   parent[k]=i; } // 递推的边界处理 for (int i=-1; i<=m; i++)   for (int j=-1; j<=n; j++)    f(i,j) = (i==-1 || j==0) ? 0: (-1); postorder(a[0].leftchild, n);  cout<<f(a[0].leftchild,n);  return 0; }