算法设计与分析-动态规划树形DP题目记录。

树形DP

树形dp

树形DP的思路是用树形结构存储数据，使用DFS更新状态数组。

树形DP一般自底向上，按子树从小到大求解，将将节点编号作为状态的第一维，表示以该节点为根的子树的解。

树形DP一般采用深度优先遍历，先求解叶子节点，向上进行状态转移，求解完当前节点的所有子树，才求解当前节点。

能够使用树形DP解决的问题的特征是每个子树的问题独立。

链式前向星图

有向树上的问题可以将树作为有向图来存储，有向图常用邻接表或静态邻接表存储。静态邻接表又称为链式前向星，使用两个数组保存所有边，head[i]表示以i为起点的最后一条边，edges[]中存储了所有的边，每个边的结构体保存了一个值last(或者常写为next)，指向相同起点的另一条边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct edge{
    int to;
    int last;
    int d;		//边权
};
int cnt = 0;	//边数
int head[maxn];
edge edges[maxk];
memset(head, -1, sizeof(head));
//添加边
void addEdge(int i, int j){
    edges[cnt].to = j;
    edges[cnt].last = head[x];
    head[x] = cnt++;
}
//遍历所有边
...
    for(int i=0;i<=n;i++){	//遍历每个点为起点的边
        for(int j=head[i];j!=-1;j=edges[j].last){
            //edges[j]为i为起点的一条边
            ...
        }
    }
...

使用链式前向星图比邻接表，vector实现的邻接表更省空间，vector扩大时会将空间扩大2倍，数据规模大时可能被卡空间或时间。

P1352 没有上司的舞会

传送门：https://www.luogu.com.cn/problem/P1352

问题描述

某大学有 n个职员，编号为 1…n1…n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r，但是如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 n。

第 22 到第 (n+1) 行，每行一个整数，第 (i+1) 行的整数表示 i 号职员的快乐指数 r。

第 (n+2) 到第 2n 行，每行输入一对整数 l,k，代表 k 是 l 的直接上司。

算法设计

用树形结构表示所有职员，节点为每个职员，直接相连的父节点为直接上司。

用dp[i][0/1]表示以节点i为根节点的子树的最优解，第二维的0/1表示当前节点的职员是否参加舞会。考虑当前节点是否选择参加：

  • 不选择当前节点u，则u的所有子节点可选可不选，因此，v为u的子节点。
  • 选择当前节点，则u的所有子节点都不可选择参加，。

对于节点u，可以初始化其子树解的下界：。

最终的结果为

使用链式前向星图(静态邻接表)存储树，有向边为父节点指向子节点的边。

代码实现

c++

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
56
57
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int maxn = 6e3+5;
struct edge{
    int to;
    int last;
};
int n, cnt = 0;         //节点数与边数
int head[maxn];         //从i出发的最后一条边
int dp[maxn][2];        //状态数组
int r[maxn];            //快乐指数
edge edges[maxn];
bool vis[maxn];         //记录是否有向上层的边, 用于找根节点

void add(int x, int y){
    edges[cnt].to = y;          //连接的点
    edges[cnt].last = head[x];  //上一条边
    head[x] = cnt++;            //当前边为从x出发的最后一条边
}

void dfs(int cur){
    dp[cur][0] = 0;
    dp[cur][1] = r[cur];
    for(int i=head[cur];~i;i=edges[i].last){
        dfs(edges[i].to);
        dp[cur][1] += dp[edges[i].to][0];
        dp[cur][0] += max(dp[edges[i].to][0], dp[edges[i].to][1]);
    }
}

int main(){
    int x, y, root;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> r[i];
    }
    //输入边
    memset(head, -1, sizeof(head));
    for(int i=1;i<n;i++){
        cin >> x >> y;
        add(y, x);
        vis[x] = 1;
    }
    //找到根节点
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            root = i;
            break;
        }
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) <<endl;
    return 0;
}

java

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Scanner;
import java.util.Arrays;

class edge{
    public int to, last;
}
class graph{
    private final int maxn = (int)6e3+5;
    private int n;
    private int root;
    private int cnt;
    private int[] head;
    private edge[] edges;
    private int[][] dp;
    private int[] r;
    public graph(int n){
        this.n = n;
        head = new int[n+1];
        edges = new edge[maxn];
        dp = new int[n+1][2];
        r = new int[n+1];
        Arrays.fill(head, -1);
        for(int i=0;i<maxn;i++) edges[i] = new edge();
    }
    public void setRoot(int r) { root = r;}
    public void setR(int i, int r) {this.r[i] = r;}
    public void add(int x, int y){
        edges[cnt].to = y;
        edges[cnt].last = head[x];
        head[x] = cnt++;
    }
    public void dfs(int cur){
        dp[cur][1] = r[cur];
        for(int i=head[cur];i!=-1;i=edges[i].last){
            dfs(edges[i].to);
            dp[cur][0] += Math.max(dp[edges[i].to][0], dp[edges[i].to][1]);
            dp[cur][1] += dp[edges[i].to][0];
        }
    }
    public void solution(){
        dfs(root);
        System.out.println(Math.max(dp[root][0], dp[root][1]));
    }
}

public class P1352{
    public static void main(String args[]){
        int n, x, y;
        int[] vis;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        graph g = new graph(n);
        vis = new int[n+1];
        //读入指数
        for(int i=1;i<=n;i++){
            g.setR(i, sc.nextInt());
        }
        //读入边
        for(int i=1;i<n;i++){
            x = sc.nextInt();
            y = sc.nextInt();
            g.add(y, x);
            vis[x] = 1;
        }
        //找到根节点
        for(int i=1;i<=n;i++){
            if(vis[i]==0){
                g.setRoot(i);
                break;
            }
        }
        g.solution();
    }
}

测试输入与输出

输入：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出：

5

318 有向树k中值问题

问题描述

给定一颗有向树T，T中每个顶点u都有一个权w(u)，树的每条边(u，v)也有一个非负边长d。有向树T的每个顶点u可以看作客户，服务需求量为w(u)。每条边的边长可以看作运输费用。如果在顶点u处为设置服务机构，则将顶点u处的服务需求沿有向树的边(u，v)转移到v处服务机构所付出的服务转移费用为w(u)*d(u，v)。树根处已设置了服务机构，现在要在树T中增设k处服务机构，使整棵树的服务转移费用最小。

对于给定的有向树T，计算在树T中增设k处服务机构的最小服务转移费用。

image-20230102103543549

输入格式

输入的第一行为两个数字n和k，n为边数，k为增设服务机构数。树有编号为0,1,…,n的节点，0为根节点。此后的n行输入每行有三个数，分别为wi，vi，di，表示顶点权，有向边(i，vi)，边长(i取1-n)。

算法设计

参考传送门：https://blog.csdn.net/RinRinko/article/details/127436260

每个子树的问题都独立，因此可以考虑树形dp。

对于每个以当前节点为根的子树，要考虑的问题如下：

  • 当前节点是否增设服务机构
  • 如果一共增设k个服务机构，子节点应该怎么分配这k个服务机构

对于第一个问题，只需要分两种情况讨论。但是第二个问题，如果使用原来的有向树处理，每个节点可能有多个子节点，遍历所有的分配情况是困难的，因此可以考虑将原来的有向树转化为一颗二叉树。

原来的树可以转化为二叉树处理的原因是，将一棵树转化为二叉树，一个节点的子节点仍然是他的子节点，因此将k个服务机构分配下去，每个节点都再进行分配，就考虑到了每个子节点分配0-k个服务机构的情况。但是转化为二叉树是为了分配服务机构，不能将原树的节点距离改变，因此要在初始的树上，把每个节点到其上层节点的距离算出来，这样计算转移费用时，仍然使用的是原来的树上的距离。

具体设计如下：

  • dp[v][u][k]：表示以v为根节点的子树，离v最近的服务节点为u且子树可增设k个服务机构的最小转移费用。第二维的设置是考虑当前节点设置不设置服务机构，如果设置，子节点距离最近的服务机构就在点v，否则不是点v，在点v的上层。
  • d[v][u]：原始有向树上任意两点的距离
  • 如果当前节点i不增设服务机构，v子树的服务需要转移到u，子节点距离最近的服务机构也是u，枚举子节点分配k个服务机构数量的所有情况，最小费用为：
  • 如果当前节点i增设服务机构，v子树的服务可以在v处理，子节点距离最近的服务机构是v，最小费用为：
  • 最终dp[v][u][k] = min{minCost1，minCost2}
  • 状态转移方向不确定，采用记忆化搜索
  • 如果子节点数量小于分配到的服务机构数量，dp[v][u][k] =0，可以不计算子树
  • 每个节点的有向边是指向父节点的，只有一条，且问题在新的二叉树解决，因此原树只需要记录每个点的父节点及距离，用于计算任意两点之间的距离
  • 如果d(v，u)不存在，即u是v的同层节点，那在u设置服务机构，v是不可以用的，因此需要将u修正为距离v最近的服务机构，且u可达。用if_serve[i]记录节点是否是服务机构，然后从v的父节点开始向上寻找最近的服务机构。

image-20230102171620549

代码实现

c++

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

//根据题意，每个点都只有一个有向边，因此边不需要存储为链式前向星图中边的格式
struct edge{
    int to;
    int d;
};
//树的相关变量
class solution{
private:
    int n, k;    
    const static int maxn = 100;                  
    edge original_edge[maxn];     //原始树的n条边
    int nodes[maxn];             //二叉树子树的节点数
    int w[maxn];                 //每个点的权重
    int binary_tree[maxn][2];    //二叉树
    int d[maxn][maxn];           //两节点的距离
    int if_serve[maxn];          //是否是服务机构
    int ***dp;                   //dp数组，有三维，需要开在堆内存
public:
    //构造开好dp数组
    solution(int n, int k){
        this->n = n;
        this->k = k;
        dp = new int**[n+1];
        for(int i=0;i<=n;i++){
            dp[i] = new int*[n+1];
            for(int j=0;j<=n;j++){
                dp[i][j] = new int[k+1];
            }
        }
        //初始化
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                for(int l=0;l<=k;l++){
                    dp[i][j][l] = INT_MAX;
                }
            }
        }
        fill(if_serve, if_serve+maxn, 0);
        if_serve[0] = 1;
        fill(binary_tree[0], binary_tree[0]+2*maxn, -1);
        fill(d[0], d[0]+maxn*maxn, INT_MAX);
    }
    ~solution(){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=k;j++){
                delete[] dp[i][j];
            }
        }
        for(int i=0;i<=n;i++) delete[] dp[i];
        delete[] dp;
    }
    //读入树并存入二叉树
    void input_tree(){
        int vi,wi,di;
        for(int i=1;i<=n;i++){
            cin >> wi >> vi >> di;
            w[i] = wi;
            original_edge[i].to = vi;
            original_edge[i].d = di;
            //存入二叉树, vi是上层父节点，i是子节点，对于转化的二叉树，左子树是子节点，右子树是同层节点
            if (binary_tree[vi][0]==-1){                   //vi没有左节点，左节点就是i
                binary_tree[vi][0] = i;
            }
            else{
                binary_tree[i][1] = binary_tree[vi][0];    //vi的左节点接到i的右节点，i作为vi的左节点
                binary_tree[vi][0] = i;
            }
        }
    }
    //初始化原树所有节点之间的距离
    void cal_dis(){
        for(int i=n;i>=0;i--){              //从原树的叶子节点向上算距离
            int dest = i, dis = 0;          
            while(dest){                    //向上到根节点
                dis += original_edge[dest].d;
                dest = original_edge[dest].to;
                d[i][dest] = d[dest][i] = dis;
            }
        }
    }
    //计算二叉树的子树的节点数
    int count_child(int node){
        nodes[node] = 1;
        if(binary_tree[node][0]!=-1){
            nodes[node] += count_child(binary_tree[node][0]);
        }
        if(binary_tree[node][1]!=-1){
            nodes[node] += count_child(binary_tree[node][1]);
        }
        return nodes[node];
    }
    //记忆化搜索
    int cal(int v, int u, int k){
        //剪枝
        if(dp[v][u][k]!=INT_MAX) return dp[v][u][k];
        if(k>nodes[v]) {
            dp[v][u][k] = 0;
            return 0;
        }
        //如果u在原来的树上不可达，那dp[v][u][k]中u是v在原树上的上层服务机构点
        if(d[v][u]==INT_MAX) u = original_edge[v].to; 
        while(if_serve[u]==0){
            u = original_edge[u].to;
        }
        //分别计算节点v设置和不设置服务机构的情况
        //不设置服务机构
        int cost;
        for(int i=0;i<=k;i++){
            cost = w[v]*d[v][u];
            if(binary_tree[v][0]!=-1){
                cost += cal(binary_tree[v][0], u, i);
            }
            if(cost > dp[v][u][k]) continue;       //剪枝
            if(binary_tree[v][1]!=-1){
                cost += cal(binary_tree[v][1], u, k-i);
            }
            dp[v][u][k] = min(dp[v][u][k], cost);
        }
        //设置服务机构, 根节点不可以设置
        if(v==0) return dp[v][u][k];
        if_serve[v] = 1;                           //当前节点设置为服务机构
        for(int i=0;i<=k-1;i++){
            cost = 0;
            if(binary_tree[v][0]!=-1){
                cost += cal(binary_tree[v][0], v, i);
            }
            if(cost > dp[v][u][k]) continue;       //剪枝
            if(binary_tree[v][1]!=-1){
                cost += cal(binary_tree[v][1], v, k-i-1);
            }
            dp[v][u][k] = min(dp[v][u][k], cost);
        }
        if_serve[v] = 0;                           //取消当前节点为服务机构
        return dp[v][u][k];
    }
    int solve(){
        input_tree();
        cal_dis();
        count_child(0);
        return cal(0, 0, k);
    }
};

int main(){
    int n, k, result;
    cin >> n >> k;
    solution s(n, k);
    result = s.solve();
    cout << result <<endl;
    return 0;
}

java

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
import java.util.Scanner;
import java.util.Arrays;

class edge{
    public int to, d;
}

class solution{
    private int n,k;
    private int[] w;
    private edge[] original_edge;
    private int[][] d;
    private int[][] binary_tree;
    private int[] nodes;
    private int[][][] dp;
    private int[] is_server;

    public void initialize(int n, int k){
        this.n = n;
        this.k = k;
        w = new int[n+1];
        original_edge = new edge[n+1];
        for(int i=0;i<=n;i++) original_edge[i] = new edge();
        d = new int[n+1][n+1];
        binary_tree = new int[n+1][2];
        nodes = new int[n+1];
        is_server = new int[n+1];
        dp = new int[n+1][n+1][k+1];
        //初始化
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                for(int l=0;l<=k;l++){
                    dp[i][j][l] = Integer.MAX_VALUE;
                }
            }
        }
        for(int i=0;i<=n;i++) binary_tree[i][0] = binary_tree[i][1] = -1;
        for(int i=0;i<=n;i++) Arrays.fill(d[i], Integer.MAX_VALUE);
        is_server[0] = 1;
    }
    //读入树并转为二叉树
    public void input_tree(){
        int wi, vi, di;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); k = sc.nextInt();
        initialize(n, k);
        for(int i=1;i<=n;i++){
            wi = sc.nextInt(); vi = sc.nextInt(); di = sc.nextInt();
            w[i] = wi;
            original_edge[i].to = vi;
            original_edge[i].d = di;
            //存入二叉树, 左子节点是原树子节点，右子节点是原树同层节点
            if(binary_tree[vi][0]==-1){
                binary_tree[vi][0] = i;
            }
            else{
                binary_tree[i][1] = binary_tree[vi][0];
                binary_tree[vi][0] = i; 
            }
        }
    }
    //计算原树中各点之间的距离
    public void cal_dis(){
        for(int i=n;i>=0;i--){
            int dest = i, dis = 0;
            while(dest!=0){
                dis += original_edge[dest].d;
                dest = original_edge[dest].to;
                d[i][dest] = dis;
            }
        }
    }
    //计算二叉树的子树的节点数
    public int count_child(int node){
        nodes[node] = 1;
        if(binary_tree[node][0]!=-1){
            nodes[node] += count_child(binary_tree[node][0]);
        }
        if(binary_tree[node][1]!=-1){
            nodes[node] += count_child(binary_tree[node][1]);
        }
        return nodes[node];
    }
    //记忆化搜索
    public int cal(int v, int u, int k){
        //剪枝
        if(dp[v][u][k]!=Integer.MAX_VALUE) return dp[v][u][k];
        if(k>nodes[v]) {
            dp[v][u][k] = 0;
            return 0;
        }
        //如果u在原来的树上不可达，那dp[v][u][k]中u是v在原树上的上层服务机构点
        if(d[v][u]==Integer.MAX_VALUE) u = original_edge[v].to; 
        while(is_server[u]==0){
            u = original_edge[u].to;
        }
        //分别计算节点v设置和不设置服务机构的情况
        //不设置服务机构
        int cost;
        for(int i=0;i<=k;i++){
            cost = w[v]*d[v][u];
            if(binary_tree[v][0]!=-1){
                cost += cal(binary_tree[v][0], u, i);
            }
            if(cost > dp[v][u][k]) continue;       //剪枝
            if(binary_tree[v][1]!=-1){
                cost += cal(binary_tree[v][1], u, k-i);
            }
            dp[v][u][k] = Math.min(dp[v][u][k], cost);
        }
        //设置服务机构, 根节点不可以设置
        if(v==0) return dp[v][u][k];
        is_server[v] = 1;                          //当前节点设置为服务机构
        for(int i=0;i<=k-1;i++){
            cost = 0;
            if(binary_tree[v][0]!=-1){
                cost += cal(binary_tree[v][0], v, i);
            }
            if(cost > dp[v][u][k]) continue;       //剪枝
            if(binary_tree[v][1]!=-1){
                cost += cal(binary_tree[v][1], v, k-i-1);
            }
            dp[v][u][k] = Math.min(dp[v][u][k], cost);
        }
        is_server[v] = 0;                           //取消当前节点为服务机构
        return dp[v][u][k];
    }
    int solve(){
        input_tree();
        cal_dis();
        count_child(0);
        return cal(0, 0, k);
    }
}

public class DP318{
    public static void main(String args[]){
        int res;
        solution s = new solution();
        res = s.solve();
        System.out.println(res);
    }
}

测试输入与输出

输入：

4 2

1 0 1

1 1 10

10 2 5

1 2 3

输出：

4

322 树的最大连通分支问题

问题描述

给定一棵树T，树中每个顶点u都有权值w(u)，可以是负数。现在要找到树T的一个连通子图使该子图的权之和最大。

设计一个算法，对于给定的树T，计算树T的最大连通分支。

输入格式

第一行有一个整数n，表示树T有n个节点，编号为1-n。第二行有n个整数，表示n个节点的权值，接下来的n-1行中，每一行有两个整数u和v，表示顶点u和顶点v相连。

算法设计

每个子树的问题都独立，可以使用树形DP。

设dp[i][0/1]表示以i为根节点的子树的最大连通分支，dp[i][0]表示不选择当前节点时，最大连通分支权值，dp[i][1]表示选择当前节点时，最大连通分支权值。

如果选择当前节点，要连接上一个子节点u，子节点u也必须选择，才能保证连通，包含当前节点的最大连通分支为：

如果不选择当前节点，包含当前节点的最大连通分支就是所有子树的最大连通分支权值：

用链式前向星图存树，将编号为1的节点作为根节点。最终的答案为max{dp[1][0]，dp[1][1]}

代码实现

c++

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

struct edge{
    int to;
    int last;
};
class solution{
private:
    const static int maxn = 1000;
    int n, cnt;
    int w[maxn];
    edge edges[maxn];
    int head[maxn];
    int dp[maxn][2];
public:
    solution(int n){
        this->n = n; 
        cnt = 0;
        fill(dp[0], dp[0] + maxn*2, INT_MIN);
        fill(head, head + maxn, -1);
    }
    //权值输入
    void setW(int i, int wi){ w[i] = wi; }
    //添加边
    void addEdge(int x, int y){
        edges[cnt].to = y;
        edges[cnt].last = head[x];
        head[x] = cnt++;
    }
    //求最大连通分支值
    void dfs(int i){
        dp[i][1] = w[i];
        for(int j=head[i];j!=-1;j=edges[j].last){
            int child = edges[j].to;
            dfs(child);
            if(dp[child][1]>0){
                dp[i][1] += dp[child][1];
                dp[i][0] = max(dp[i][0], max(dp[child][0], dp[child][1]));
            }
        }
    }
    int solve(){
        dfs(1);
        return max(dp[1][0], dp[1][1]);
    }
};

int main(){
    int n, x, y, res;
    cin >> n;
    solution s(n);
    for(int i=1;i<=n;i++){
        cin >> x;
        s.setW(i, x);
    }
    for(int i=1;i<=n-1;i++){
        cin >> x >> y;
        if(x>y){
            s.addEdge(y, x);
        }
        else{
            s.addEdge(x, y);
        }
    }
    res = s.solve();
    cout << res << endl;
    return 0;
}

java

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.Scanner;
import java.util.Arrays;

class edge{
    int to, last;
}

class solution{
    private int n, cnt;
    private int[] w;
    private int[] head;
    private edge[] edges;
    private int[][] dp;

    public solution(int n){
        this.n = n;
        cnt = 0;
        w = new int[n+1];
        head = new int[n+1];
        dp = new int[n+1][2];
        edges = new edge[n];
        for(int i=0;i<n;i++) edges[i] = new edge();
        Arrays.fill(head, -1);
        for(int i=0;i<=n;i++) dp[i][0] = dp[i][1] = Integer.MIN_VALUE;
    }
    //设定权重
    public void setW(int x, int wi){ w[x] = wi; }
    //添加边
    public void addEdge(int x, int y){
        edges[cnt].to = y;
        edges[cnt].last = head[x];
        head[x] = cnt++;
    }
    //dfs填表求最大连通分支
    public void dfs(int i){
        dp[i][1] = w[i];
        for(int j=head[i];j!=-1;j=edges[j].last){
            int child = edges[j].to;
            dfs(child);
            if(dp[child][1]>0) dp[i][1] += dp[child][1];
            dp[i][0] = Math.max(dp[i][0], Math.max(dp[child][0], dp[child][1])); 
        }    
    }
    public int solve(){
        dfs(1);
        return Math.max(dp[1][0], dp[1][1]);
    }
}

public class DP322{
    public static void main(String args[]){
        int n, x, y, res;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        solution s = new solution(n);
        for(int i=1;i<=n;i++){
            x = sc.nextInt();
            s.setW(i, x);
        }
        for(int i=1;i<=n-1;i++){
            x = sc.nextInt(); y = sc.nextInt();
            if(x>y){
                s.addEdge(y, x);
            }
            else{
                s.addEdge(x, y);
            }
        }
        res = s.solve();
        System.out.println(res);
    } 
}

测试输入与输出

输入：

5

-1 1 3 1 -1

4 1

1 3

1 2

4 5

输出：

4

P2015 二叉苹果树

题目描述

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。

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

1
2
3
4
5
2   5
 \ / 
  3   4
   \ /
    1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

输入与输出格式

输入

第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。

接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。

输出

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

样例输入与输出

输入

1
2
3
4
5
5 2
1 3 1
1 4 10
3 2 20
3 5 20

输出

1
21

提示

$1 \leqslant Q < N \leqslant 100$，每根树枝上的苹果 $\leqslant 3 \times 10^4$。

算法设计

将树枝的苹果数记入树形结构节点。

用dp[i][j]表示到编号i为根节点的子树保留j个树枝的最大苹果数，采用dfs的方式进行记忆化搜索。如果i为叶子节点，则其保留树枝为1时最大苹果数就是自身苹果数，对于非叶子节点，递推方程为：

j取不到，因为节点本身占了一个树枝，如果是根节点则不占用。

代码实现

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
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.StreamTokenizer;
import java.io.IOException;

public class Main{
    private static int n, q;
    private static int[] apples;
    private static int[][] tree;
    private static int[][] dp;
    public static void main(String args[]) throws IOException {
        Reader r = new Reader();
        n = r.nextInt(); q = r.nextInt();
        apples = new int[n+1];
        tree = new int[n+1][2];
        dp = new int[n+1][q+1];
        for(int i=1;i<=n;i++) tree[i][0] = tree[i][1] = -1;
        for(int i=1;i<=n-1;i++){
            int parent, child, num_apples;
            parent = r.nextInt(); child = r.nextInt(); num_apples = r.nextInt();
            if(tree[parent][0]==-1) tree[parent][0] = child;
            else tree[parent][1] = child;
            apples[child] = num_apples;
        }
        int result = _dp(1, q);
        System.out.println(result);
    }
    public static int _dp(int i, int j){
        if(dp[i][j]!=0) return dp[i][j];
        if(tree[i][0]==-1||tree[i][1]==-1){
            dp[i][j] = (j>=1)?apples[i]:0;
            return dp[i][j]; 
        }
        int num = (i==1)?j:j-1;
        for(int k=0;k<=num;k++){
            dp[i][j] = Math.max(dp[i][j], _dp(tree[i][0], k)+_dp(tree[i][1], num-k)+apples[i]);
        }
        return dp[i][j];
    }
}

class Reader{
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}

P2014 选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

输入与输出格式

输入

第一行有两个整数 $N$ , $M$ 用空格隔开。( $1 \leq N \leq 300$ , $1 \leq M \leq 300$ )

接下来的 $N$ 行,第 $I+1$ 行包含两个整数 $k_i $和 $s_i$, $k_i$ 表示第I门课的直接先修课，$s_i$ 表示第I门课的学分。若 $k_i=0$ 表示没有直接先修课（$1 \leq {k_i} \leq N$ , $1 \leq {s_i} \leq 20$）。

输出

只有一行，选 $M$ 门课程的最大得分。

样例输入与输出

输入

1
2
3
4
5
6
7
8
7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

输出

1
13

算法设计

该问题类似于背包问题。

设dp[i][j]表示第i个节点为根的子树可以选j种课的最大学分，对于每个子节点的子树，都可以选择放入或不放入，递推方程为：

i为当前节点，v为子节点，当前节点只要j>1必选，才能考虑选子节点。

使用链式前向星存储树，因为有多棵树，以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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.io.IOException;

public class Main{
    static class edge{
        public int to,last;
    }
    public static int n, m, cnt;
    public static int[] score;
    public static int[] head;
    public static edge[] edges;
    public static int[][] dp;
    public static void main(String args[]) throws IOException {
        Reader r = new Reader();
        n = r.nextInt(); m = r.nextInt();
        cnt = 0;
        score = new int[n+1];
        head = new int[n+1];
        edges = new edge[305];
        dp = new int[n+1][m+2];
        Arrays.fill(head, -1);
        for(int i=1;i<=n;i++){
            int pre, s;
            pre = r.nextInt(); s = r.nextInt();
            add(pre, i);
            score[i] = s;
        }
        for(int i=1;i<=n;i++) dp[i][1] = score[i];
        dfs(0);
        System.out.println(dp[0][m+1]);
    }
    public static void add(int x, int y){
        edges[cnt] = new edge();
        edges[cnt].to = y;
        edges[cnt].last = head[x];
        head[x] = cnt++;
    }
    public static void dfs(int i){
        for(int x=head[i];x!=-1;x=edges[x].last){
            int child = edges[x].to;
            dfs(child);
            for(int j=m+1;j>=1;j--){
                for(int k=0;k<j;k++){
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-k]+dp[child][k]);
                }
            }
        }
    }
}

class Reader{
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}

P2585 三色二叉树

题目描述

一棵二叉树可以按照如下规则表示成一个由 $0$、$1$、$2$ 组成的字符序列，我们称之为“二叉树序列 $S$”：

例如，下图所表示的二叉树可以用二叉树序列 $S=\texttt{21200110}$ 来表示。

haha.png

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不同。给定一颗二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入与输出格式

输入

输入只有一行一个字符串 $s$，表示二叉树序列。

输出

输出只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

样例输入与输出

输入

1
1122002010

输出

1
5 2

提示

对于全部的测试点，保证 $1 \leq |s| \leq 5 \times 10^5$，$s$ 中只含字符 0 1 2。

算法设计

可以使用dp[i][j]表示点i为根节点的子树最多有多少个点可以被染成绿色，j为1表示节点i为绿色。

如果i为绿色，则其子节点都不可以为绿色；如果i不为绿色，则要选择两个子节点其中一个染为绿色，故递推方程为：

将二叉树序列处理为数组存储的二叉树，然后以记忆化搜索的方式完成计算，最终的结果为dp[1]。

最少数量类似。

代码实现

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.io.IOException;

public class Main{
    public static final int maxn = 500005;
    public static String orignal_tree;
    public static int n, cnt, cur;
    public static int[][] tree;
    public static int[][] dp;
    public static int[][] dpMin;
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        orignal_tree= bf.readLine();
        cnt = 0; cur = 1; n = 1;
        tree = new int[maxn][2];
        dp = new int[maxn][2];
        dpMin = new int[maxn][2];
        for(int i=1;i<maxn;i++) tree[i][0] = tree[i][1] = dp[i][0] = dp[i][1] = dpMin[i][0] = dpMin[i][1] = -1;
        load_tree(1);
        //搜索
        int resultMax = Math.max(dfs(1, 0), dfs(1, 1));
        int resultMin = Math.min(dfsMin(1, 0), dfsMin(1, 1));
        System.out.println(resultMax+" "+resultMin);
    }
    //序列化二叉树转储到数组
    public static void load_tree(int i){
        char childs = orignal_tree.charAt(cnt++);
        if(childs>='1'){
            tree[i][0] = ++cur;
            load_tree(cur);
            n++;
        }
        if(childs=='2'){
            tree[i][1] = ++cur;
            load_tree(cur);
            n++;
        }
        return;
    }
    //记忆化搜索
    public static int dfs(int i, int j){
        if(i==-1) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(j==0){   //节点i不是绿色
            dp[i][j] = Math.max(dfs(tree[i][0],1)+dfs(tree[i][1], 0), dfs(tree[i][0],0)+dfs(tree[i][1], 1));
        }
        else{       //节点i是绿色
            dp[i][j] = 1 + dfs(tree[i][0], 0) + dfs(tree[i][1], 0);  
        }
        return dp[i][j];
    }
    //
    public static int dfsMin(int i, int j){
        if(i==-1) return 0;
        if(dpMin[i][j]!=-1) return dpMin[i][j];
        if(j==0){   //节点i不是绿色
            dpMin[i][j] = Math.min(dfsMin(tree[i][0],1)+dfsMin(tree[i][1], 0), dfsMin(tree[i][0],0)+dfsMin(tree[i][1], 1));
        }
        else{       //节点i是绿色
            dpMin[i][j] = 1 + dfsMin(tree[i][0], 0) + dfsMin(tree[i][1], 0);  
        }
        return dpMin[i][j];
    }
}

class Reader{
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}

P2656 采蘑菇

题目描述

小胖和 ZYR 要去 ESQMS 森林采蘑菇。

ESQMS 森林间有 $N$ 个小树丛，$M$ 条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。小胖和 ZYR 经过某条小径一次，可以采走这条路上所有的蘑菇。由于 ESQMS 森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，再下取整。

比如，一条路上有 $4$ 个蘑菇，这条路的“恢复系数”为 $0.7$，则第一~四次经过这条路径所能采到的蘑菇数量分别为 $4,2,1,0$。

现在，小胖和 ZYR 从 $S$ 号小树丛出发，求他们最多能采到多少蘑菇。

输入与输出格式

输入

第一行两个整数，$N$ 和 $M$。

第二行到第 $M+1$ 行，每行四个数，分别表示一条小路的起点，终点，初始蘑菇数，恢复系数。

第 $M+2$ 行，一个整数 $S$。

输出

一行一个整数，表示最多能采到多少蘑菇，保证答案不超过 $(2^{31}-1)$。

样例输入与输出

输入

1
2
3
4
5
3 3
1 2 4 0.5
1 3 7 0.1
2 3 4 0.6
1

输出

1
8

提示

对于 $30\%$ 的数据，$N\le 7$，$M\le15$

另有 $30\%$ 的数据，满足所有“恢复系数”为 $0$。

对于 $100\%$ 的数据，$1
\le N\le 8\times 10^4$，$1\le M\le 2\times 10^5$，$0\le\text{恢复系数}\le 0.8$ 且最多有一位小数， $1\le S\le N$。

算法设计

设dp[i]表示以当前节点为根的子树能采集的最大蘑菇数。假设节点u有子节点v，递推方程为：

即在每个根节点选择一个能得到蘑菇数最大的子节点为根的子树走下去。

处理环路的方式是每经过一次就修正蘑菇数，一个蘑菇数为0的节点走过两次，说明产生了环路，此时开始记录环路上的蘑菇数