水题笔记_ luogu2014 选课 [树形DP]

经典的题要敢于有不同的做法

懵逼的 题目

传送至 luogu

扯淡的 题解

树形DP…经典题目没什么好说的
然后我打了个普通树形DP × 奇怪的背包(忘了叫啥惹)
TLE TLE
然后就放下了…今天loli突然让打这道于是就用了那个什么 [左儿子右兄弟] 做了一波
TLE TLE
然后Refun真dalao让我在大牛上交一遍….就TM过了…
然后把第一次的那个树形 × 背包交了一遍…也TM过了…
跑的还比第一个快…
一开始在CV上交过了还以为CV数据水
现在才知道是LG测评姬慢 CTL

沙茶的 代码

树形 × 背包

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (300 + 5)
#define INF (6000)
const int root = 0;
using namespace std;
struct edg
{
int from;
int to;
int next;
} b[MAXN];
int cntb = 0;
int g[MAXN];

int n, m;
int w[MAXN];
int du[MAXN];
int fa[MAXN];
int f[MAXN][MAXN];
int fv[MAXN];

int dfs(int, int);// dfs(i, j)以 i 为根, 选 j 门课最大的收益
void adn(int, int);
int bb(int, int);//
int main()
{
memset(f, -1, sizeof(f));
scanf("%d%d", &n, &m);
int srx, sry;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, i);
fa[i] = srx;
w[i] = sry;
}
int ans = dfs(root, m + 1);
printf("%d", ans);
return 0;
}
void adn(int fr, int to)
{
b[++cntb].next = g[fr];
b[cntb].from = fr;
b[cntb].to = to;
g[fr] = cntb;
}
int dfs(int dq, int dqm)
{
f[dq][0] = 0;
f[dq][1] = w[dq];
f[dq][dqm] = w[dq];
dqm--;
for (int i = g[dq]; i; i = b[i].next)
{
for (int j = 0; j <= dqm; j++)
if (f[b[i].to][j] == -1)
{
dfs(b[i].to, j);
if (f[b[i].to][j] == -1)
{
f[b[i].to][j] = -INF;
}
}
}
dqm++;
f[dq][dqm] += bb(dq, dqm - 1);
return f[dq][dqm];
}
int bb(int r, int v)
{
memset(fv, 0, sizeof(fv));
for (int i = g[r]; i; i = b[i].next)
{
for (int j = v; j >= 1; j--)
{
for (int k = 1; k <= j; k++)
{
fv[j] = max(fv[j], fv[j - k] + f[b[i].to][k]);
}
}
}
return fv[v];
}

/*
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
*/

/*
10 5
0 4
0 6
1 2
0 1
2 8
4 9
3 7
5 1
8 2
2 4
*/

[左儿子右兄弟]

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
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define MAXN (300 + 5)
#define INF (6000 + 5)
#define NON (301)
const int root = 0;
using namespace std;
struct node
{
int left;
int right;
int w;
}b[MAXN];
int f[MAXN][MAXN];
int n, m;
int ans;
int dfs(int, int);
void adn(int, int);
void init();
int main()
{
init();
ans = dfs(root, m + 1);
printf("%d", ans);
return 0;
}

void init()
{
memset(f, -1, sizeof(f));
scanf("%d%d", &n, &m);
int srx, sry;
for (int i = 0; i <= n; i++)
{
b[i].right = b[i].left = NON;
}
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, i);
f[i][0] = 0;
b[i].w = sry;
}
f[NON][0] = 0;
int bro;
for (int i = 1; i <= n; i++)
{
bro = i;
int maxw = -INF;
while (bro != NON)
{
maxw = max(maxw, b[bro].w);
bro = b[bro].right;
}
f[i][1] = maxw;
}
}

void adn(int fr, int to)
{
if (b[fr].left == NON)
{
b[fr].left = to;
}
else
{
int x = b[fr].left;
while (b[x].right != NON)
{
x = b[x].right;
}
b[x].right = to;
}
}

int dfs(int dq, int dqm)
{
if (f[dq][dqm] != -1)
{
return f[dq][dqm];
}
if (!dqm)
{
return f[dq][dqm] = 0;
}
if (dq == NON)
{
return f[dq][dqm] = -INF;
}
/*if (dqm == 1)
{
return f[dq][dqm] = max(b[dq].w, dfs(b[dq].right, dqm));
}*/
f[dq][dqm] = max(f[dq][dqm], max(dfs(b[dq].right, dqm), dfs(b[dq].left, dqm - 1) + b[dq].w));
for (int i = 1; i < dqm; i++)
{
f[dq][dqm] = max(f[dq][dqm], dfs(b[dq].left, i - 1) + b[dq].w + dfs(b[dq].right, dqm - i));
}
return f[dq][dqm] = max(f[dq][dqm], f[b[dq].right][dqm]);
}

/*
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
*/

/*
50 20
0 8
1 6
2 10
0 10
4 10
5 6
3 5
0 10
3 10
0 4
5 8
0 2
6 8
0 10
12 10
10 6
11 5
12 6
12 8
6 8
13 9
13 1
5 8
15 4
16 2
18 2
12 2
21 6
22 4
28 3
24 2
10 9
22 2
24 4
8 5
24 5
8 9
23 6
14 8
36 7
17 7
6 6
12 5
16 8
3 8
27 8
38 9
38 10
42 10
36 5
*/

By 文化课爆炸的 Cansult