DAY7（DP进阶）
POJ - 2342 Anniversary party（树形DP）
入门树形DP。
用vector将边存下来，然后将一个点作为树的根节点进行dp，d[x][0]表示编号为x的员工不参加的愉悦值，d[x][1]表示编号为x的员工参加的愉悦值。v节点表示x节点所连的边，转移方程为：d[x][1] += d[v][0]; d[x][0] += max(d[v][1], d[v][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
| #include<vector>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll maxn = 6010;
ll n, u, v;
ll d[maxn][2];
bool vis[maxn];
vector<int> son[maxn];
void dfs(int x) {
vis[x] = 1;
for (int i=0;i<son[x].size();++i) {
int v = son[x][i];
if (!vis[v]) {
dfs(v);
d[x][1] += d[v][0];
d[x][0] += max(d[v][1], d[v][0]);
}
}
}
int main() {
while(cin >> n) {
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));
for (int i=1;i<=n;++i) {
cin >> d[i][1];
d[i][0] = 0;
son[i].clear();
}
while(cin >> u >> v && !(u == 0 && v == 0)) {
son[u].push_back(v);
son[v].push_back(u);
}
dfs(1);
cout << max(d[1][0], d[1][1]) << endl;
}
return 0;
}
|
LibreOJ - 10156 战略游戏（树形DP）
和上一道题很像，d[x][0]表示x站点处没有哨兵所需要的消耗，d[x][1]表示x站点处有哨兵所需要的消耗。转移方程做了一点小小的改动： d[x][0] += d[v][1]; d[x][1] += min(d[v][1], d[v][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
| #include<vector>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll maxn = 6010;
ll n, u, v, k;
ll d[maxn][2];
bool vis[maxn];
vector<int> son[maxn];
void dfs(int x) {
vis[x] = 1;
for (int i=0;i<son[x].size();++i) {
int v = son[x][i];
if (!vis[v]) {
dfs(v);
d[x][0] += d[v][1];
d[x][1] += min(d[v][1], d[v][0]);
}
}
}
int main() {
while(cin >> n) {
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));
for (int i=1;i<=n;++i) {
cin >> u >> k;
d[u][1] = 1;
d[u][0] = 0;
for (int i=1;i<=k;++i) {
cin >> v;
son[u].push_back(v);
son[v].push_back(u);
}
}
dfs(0);
cout << min(d[0][0], d[0][1]) << endl;
}
return 0;
}
|
