说在前面

树形动态规划其实就是在树上进行其他的DP，不过存储由线性的一个数组变成了一个树结构，不过本质还是需要用到各种动态规划的，下面是几道题目：

P1300加分二叉树

题目描述：

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

  • 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。

输入:

  1. 第1行：一个整数n（n＜30），为节点个数。
  2. 第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

输出：

  1. tree的最高加分
  2. tree的前序遍历

题解：

其实这道题就是披着数规的皮，心是区间动态规划的心，我们需要在中序遍历的基础上进行区间动态规划就行，如果你建立一个图，就可以明白这样为什么可以了，在DP的过程中，要记录下来对于区间x，y的最优值是由i到k和k到j得到的k值，这样的话求前序遍历的时候我们就可以根据k为根节点，结合中序遍历就能够求出前序遍历了。

所以说有时候遇到一些题目，需要仔细想一想这些题的本质是什么类型的，不要被外表所迷惑，有可能就是披着各种复杂算法的皮，但是本质很简单。

代码：

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<ctime>
#include<queue>
#include<vector>
#include<iomanip>
using namespace std;
int n,a[100],f[100][100];
int Root[100][100],This;
void Get(int x,int y)
{
    cout<<Root[x][y]<<' ';
    if(x<=Root[x][y]-1&&Root[x][y]-1>0)
    Get(x,Root[x][y]-1);
    if(Root[x][y]+1<=y&&Root[x][y]+1<=n)
    Get(Root[x][y]+1,y);
}
int main()
{
    memset(Root,0,sizeof(Root));
    cin>>n;
    for(int i=0;i<=n+1;i++)
    for(int j=0;j<=n+1;j++)
    f[i][j]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i][i]=a[i];
        Root[i][i]=i;
    }
    for(int k=2;k<=n;k++)
    for(int i=1;i+k-1<=n;i++)
    {
        int j=i+k-1;
        for(int m=i;m<=j;m++)
        if(f[i][j]<f[i][m-1]*f[m+1][j]+a[m])
        {
             f[i][j]=f[i][m-1]*f[m+1][j]+a[m];
             Root[i][j]=m;
        }
    }
    cout<<f[1][n]<<endl;
    Get(1,n);
    return 0;
}

P1303苹果二叉树

题目描述

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果

输入:

第1行2个数，N和Q(1<=Q<= N,1<N<=100)。N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。

输出：

一个数，最多能留住的苹果的数量。

题解：

这道题是一道典型的二叉树树规的题目，二叉树其实是比较简单的，存储非常方便，我们只用一个二维数组 a[30000][2] 表示对于一个根i，其左孩子是0，右孩子是1，然后递归访问，用 f[i][j] 表示对于根节点i，保留j条边所能获得的最大苹果数量。那么DP思路就出来了，f[i][j] 中的保留j条边由左孩子和右孩子提供，枚举每个孩子提供边的数量，然后取最大值就好，注意这里需要递归返回对于根节点i，其子树上一共有多少条边，这样可以确定枚举范围，然后要注意一下两棵树分别的边数，避免出现无法达到的情况。

DP方程用有三种情况：

1.左子树一个也不提供，右子树提供数量大于零；

2.左子树提供数量大于零，右子树一个也不提供；

3.两个字数的提供数量都大于零。

（对于两个都不提供的，由于f的初始值是零，可以不作处理）

代码：

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
int n,q,Apple[200][200],f[200][200];
int x,y,v,Tree[200][3],This;
bool Get[200];
int DFS(int x)
{
    if(x==0) return 0;
    int Left=DFS(Tree[x][1]);
    int Right=DFS(Tree[x][2]);
    int all=Left+Right;
    for(int i=1;i<=all;i++)
    for(int k=0;k<=min(Left,i);k++)
    {
        if(i-k>Right) continue;
        if(i-k>0&&k>0)
        f[x][i]=max(f[x][i],f[Tree[x][1]][k-1]+f[Tree[x][2]][i-k-1]+Apple[x][Tree[x][1]]+Apple[x][Tree[x][2]]);
        if(k==0&&i-k>0) f[x][i]=max(f[x][i],f[Tree[x][2]][i-k-1]+Apple[x][Tree[x][2]]);
        if(k>0&&i-k==0) f[x][i]=max(f[x][i],f[Tree[x][1]][k-1]+Apple[x][Tree[x][1]]);
    }
    return all+1;
}
int main()
{
    memset(Apple,0,sizeof(Apple));
    memset(Tree,0,sizeof(Tree));
    memset(f,0,sizeof(f));
    memset(Get,false,sizeof(Get));
    Get[1]=true;
    cin>>n>>q;
    for(int i=1;i<=n-1;i++)
    {
        cin>>x>>y>>v;
        if(Get[y]) swap(x,y);
        Get[y]=true;
        Apple[x][y]=v;
        Apple[y][x]=v;
        if(!Tree[x][1])
        Tree[x][1]=y;
        else Tree[x][2]=y;
    }
    This=DFS(1);
    cout<<f[1][q]<<endl;
    return 0;
}

P1304选课

题目描述：

学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分.在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。

你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

输入：

输入文件的第一行包括两个整数N、M（中间用一个空格隔开），其中1≤N≤300,1≤M≤N。 以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

输出：

只有一个数：实际所选课程的学分总数。

题解：

这道题写起来是在是崩溃，DFS到了现在我的代码能力还是弱的一批，两次写都把大量的时间花在了调试上面QAQ，以后如果去写一道题的时候没有非常清晰的思路并且可以证明这种思路基本上不会出现任何问题不会被各种特殊情况卡成错误并且自己能在纸上写出框架其中的每一个元素都有详细的计算过程在脑子里构思过的话，我是不回开始去敲这道题的！！！说到做到!

这道题刚开始的时候我就直接是用DFS计算 f[i][j] 对于节点i保留j个最大值，我是从第一个节点直接开始计算，然后计算完毕之后开始DFS，关于需要前面的节点我都是找一条最长路径，结果很显然的错了QAQ。

然后我就默默的开始看题解了，发现这里DFS是先开始的，然后再计算，也就是说对于节点 f[i][j] 是从叶节点直接开始计算的，然后反推出来根节点，这里因为选择里面是有很多种情况，所以在计算的时候不能简单的将边排序，然后要几个取几个的，因为考虑到有子节点是属于根节点的，所以说子节点下面还有根节点，也是可以构成最优解，所以说我们需要再次列出来一个数组 Get[i][j] 表示的是对于根节点x的前i个子节点（注意这里计算的只有子节点），选择j个的最优值，用另外一个k循环来找到当只去 k-1 个根的时候，第k个根包括下面的子树来贡献出来 j-k+1 个点。

求出来Get之后，我们就可以很好的求出 f[i][j] 了，那么对于当前的x节点，选择j的点的时候，是 Get[all][j-1]+Value[x] ，Value表示根x的权值，all表示的是x节点儿子的个数。

具体的方法就是多叉树转二叉树然后进行计算，这样的的话写法很简便，但是对于多叉树转二叉树来说只有见到上面黄学长写出来的代码的复杂度比较第，我再次写出来的多叉树转二叉树反而效率非常低，比之前写出来的多叉树上面进行动态规划还要慢，更不要和黄学长的代码比了，但是苦恼于看不懂黄学长的代码，代码可读性果然和实力成反比的啊……

然后就是如何进行多叉树转二叉树的方法：我们建立两个数组，Child和Brother，这两个数组分别表示对于节点 i 来说，自己的孩子和自己的兄弟，这样的话就建成了一个二维数组，然后我们进行DFS寻找，表示如果要选择当前节点，那么就DFS(Child[x],y-i-1)，如果不选择当前节点，那么就把主动权交给下一位可爱的兄弟DFS(Borther[x],i)，那么这样下去我们就利用了传递性将所有的情况都传递了下去（可能就是因为这种DFS过程太多了导致时间有些长，但是代码本身还是很简单的，从开始敲到结束也就不到二十分钟，相对于我自己写的在多叉树上进行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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct Edge
{
    int Point;
    int Next;
}a[400];
int n,m,Link[400],Value[400],son[400];
int y,len=0,f[400][400],num[400],Get[400][400];
bool vis[400];
int DFS(int x)
{
    int all=0,now=0,Plus=0;
    if(vis[x]) return 0; else vis[x]=true;
    for(int i=Link[x];i;i=a[i].Next) all+=DFS(a[i].Point);
    son[x]=all;
    memset(Get,0,sizeof(Get));
    for(int i=Link[x];i;i=a[i].Next)
    {
        now++; Plus+=son[a[i].Point]+1;
        for(int j=1;j<=Plus;j++)
        {
            Get[now][j]=Get[now-1][j];
            for(int k=1;k<=min(son[a[i].Point]+1,j);k++)
            Get[now][j]=max(Get[now][j],Get[now-1][j-k]+f[a[i].Point][k]);
        }
    }
    for(int i=1;i<=all+1;i++)
    f[x][i]=Get[now][i-1]+Value[x];
    return all+1;
}
int main()
{
    memset(f,0,sizeof(f));
    memset(Link,0,sizeof(Link));
    memset(vis,false,sizeof(vis));
    memset(num,0,sizeof(num));
    memset(son,0,sizeof(son));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>y>>Value[i];
        a[++len].Point=i;
        a[len].Next=Link[y];
        Link[y]=len;
        num[y]++;
    }
    DFS(0);
    cout<<f[0][m+1]<<endl;
    return 0;
}

这种方法就是在多叉树上直接进行动态规划，这种方法十分粗暴，但是并不简单（只是我的方法），然后我再博客上看到黄学长写出来的代码之后，我就震惊了，没有多叉树转二叉树，但是代码十分精简，并且复杂度只有O(nm)，比我写出来的O(nn*m)不知道高到哪里去了！

下面是黄学长的代码（Linux下面需要附上初始值）：

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
#include<iostream>
using namespace std;
int n,m,t=0;
int v[301],s[301],ount[301];
int a[301][301],f[301][301];
int list[301];
int tree_traversal(int k)
{
    list[++t]=k;
    if(s[k]==0){return ++ount[k];}
    for(int i=1;i<=s[k];i++)
       ount[k]+=tree_traversal(a[k][i]);
    return ++ount[k];
}
int main()
{
	cin>>n>>m;
    for(int i=1;i<=n;i++){
		int x;
		cin>>x>>v[i];
		a[x][++s[x]]=i;
	}
    tree_traversal(0);
    for(int i=1;i<=n+1;i++)
		f[i][1]=v[list[i]];
    for(int i=n+1;i>=1;i--)
       for(int j=2;j<=m+1;j++)
		f[i][j]=max(f[i+1][j-1]+v[list[i]],f[i+ount[list[i]]][j]);
    cout<<f[1][m+1]<<endl;
    return 0;
}

我的多叉转二叉的做法：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,Value[600],Brother[600],x;
int f[600][600],Child[600];
void DFS(int x,int y)
{
    if(f[x][y]>=0) return;
    if(x==0||y==0)
    {
        f[x][y]=0;
        return;
    }
    DFS(Brother[x],y);
    for(int i=0;i<y;i++)
    {
        DFS(Brother[x],i);
        DFS(Child[x],y-i-1);
        int This=max(f[Brother[x]][y],f[x][y]);
        f[x][y]=max(This,f[Brother[x]][i]+f[Child[x]][y-i-1]+Value[x]);
    }
}
int main()
{
    memset(f,-1,sizeof(f));
    memset(Child,0,sizeof(Child));
    memset(Brother,0,sizeof(Brother));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>Value[i];
        Brother[i]=Child[x];
        Child[x]=i;
    }
    DFS(Child[0],m);
    cout<<f[Child[0]][m]<<endl;
    return 0;
}