有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径计数问题

树形遍历

例题: https://www.luogu.com.cn/problem/P4017 采用bfs + 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
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 5050;

int n, m, num = 80112002;
int g[maxn][maxn], f[maxn], in[maxn], out[maxn];

int main() {
int ans = 0;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
g[y][x] = 1;
in[x]++; out[y]++;
}
queue<int> q;
for(int i=1;i<=n;i++) if(in[i]==0) q.push(i),f[i]=1;//找到入度为0的点,即起点
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=1;i<=n;i++){//遍历x的所有出边
if(g[x][i]){
in[i]--;//入度减一
f[i] = (f[i] + f[x]) % num;//状态转移方程
if(in[i] == 0){
q.push(i);
if(out[i] == 0) ans=(ans + f[i]) % num;//更新答案
}
}
}
}
cout << ans;
return 0;
}

没有上司

例题: https://www.luogu.com.cn/problem/P1352
这道题主要是每个节点有两个状态,需要注意状态方程的书写,此外编写代码方便由于有两个状态,所以不适合把参数放在dp函数中,可以把dp函数分离出来

$$\begin{array}{c} f(i, 0)=\sum \max \{f(x, 1), f(x, 0)\} \qquad f(i, 1)=\sum f(x, 0)+a_{i} \end{array}

<!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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 6010;
int n;
int r[maxn] ,vis[maxn], f[maxn][2];
vector<int> son[maxn];

int dp(int x){
f[x][1] = r[x];
f[x][0] = 0;
for (int i = 0; i < son[x].size(); i++){
int s = son[x][i];
dp(s);
f[x][0] += max(f[s][0], f[s][1]);
f[x][1] += f[s][0];
}
return max(f[x][0], f[x][1]);
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++)
cin >> r[i];
for (int i = 1; i <= n; i++){
int x, y; cin >> x >> y;
son[y].push_back(x);

}
int sum = 0;
for (int i = 1; i <= n; i++){
memset(f, 0 , sizeof(f));
sum = max(sum, dp(i));
}
cout << sum;
return 0;
}


评论




Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

loading...loading... , total visits times