树形dp

树形dp就是在树的结构上用动态规划,主要用DFS。

1
dp[i][j][0/1],其中i指以i为根的子树,j指在以i为根的子树中选择j个子节点,0表示不选这个节点,1表示选择这个节点。有时候j或0/1这一维可以压掉。

基本方程:

选择节点类

1
2
dp[i][0] = dp[j][1]
dp[i][1] = max/min(dp[j][0], dp[j][1])

树形背包类

1
2
dp[v][k] = dp[u][k] + val
dp[u][k] = max(dp[u][k], dp[v][k-1])

入门题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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 6005;
int n, root, r[maxn], f[maxn][2], v[maxn]; //f记录快乐指数总和;v表示visited,用于找root;r存储每个人的快乐指数
vector<int>s[maxn];
void dp(int x){
f[x][0] = 0;
f[x][1] = r[x];
for(int i = 0; i < s[x].size(); i++){
int t = s[x][i];
dp(t); //dfs
f[x][0] += max(f[t][0], f[t][1]); //上司没来,直接下属想来就来
f[x][1] += f[t][0]; //上司来了,直接下属一定不来
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> r[i];
int l, k;
memset(v, 0, sizeof(v));
for(int i = 1; i <= n-1; i++){
cin >> l >> k;
s[k].push_back(l);
v[l] = 1;
}
for(int i = 1; i <= n; i++)
if(!v[i]){
root = i;
break;
}
dp(root);
cout << max(f[root][0], f[root][1]) << endl;
return 0;
}

参考资料

动态规划算法

动态规划算法

1. 背包问题

1.1 01背包问题

约束条件是:给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。

题目链接

典型的01背包问题。骨头的数量已知,接下来又知道了每个骨头的价值和体积,这就相当于每种物品只有一个,对每种物品只需考虑选与不选两种情况。并且,体积的限制是不能超过背包的容积V。很容易想到以下做法:

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
//定义状态dp[i][j]表示前i个物品所占的体积为j,dp[i][j]中记录这个状态能够取得的最大值。
//w[i]表示物品价值,v[i]表示物品体积
//状态转移方程为:dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 1005;
int w[maxn], v[maxn], dp[maxn][maxn];

int main(){
int T, N, V;
cin >> T;
while(T--){
cin >> N >> V;
int i, j;
for(i = 1; i <= N; i++) cin >> w[i];
for(i = 1; i <= N; i++) cin >> v[i];
memset(dp, 0, sizeof(dp));
for(i = 1; i <= N; i++){
for(j = 0; j <= V; j++){ //注意:V可以为0。
if(j >= v[i])
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
else
dp[i][j] = dp[i - 1][j];
}
}
cout << dp[N][V] << endl;
}
return 0;
}

上述做法的确AC了。但是,这里的N,V最大只有1000,一旦变得更大了,开一个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
/*
首先,我们发现dp[i][j]只与dp[i-1][j]和dp[i-1][j-v[i]]有关。也就是说,前i个物品所占体积只与前i-1个物品有关。而一旦计算了第i行所有的dp[i][j],那么第i-1行就没有作用了,因为每一行只会参考其上一行的dp[i][j]。
于是,对于dp[i-1][j],如果能够通过dp[i][k](k>=j)已经被计算就可知dp[i-1][j]的值将不再被使用,那么就将dp[i][j]存在
dp[i-1][j]中。这时令j从V到0递减,将dp[i][j]的值覆盖dp[i-1][j]即可。
所以,dp转化为了一维数组。
*/
#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 1005;
int w[maxn], v[maxn], dp[maxn];

int main(){
int T, N, V;
cin >> T;
while(T--){
cin >> N >> V;
int i, j;
for(i = 1; i <= N; i++) cin >> w[i];
for(i = 1; i <= N; i++) cin >> v[i];
memset(dp, 0, sizeof(dp));
for(i = 1; i <= N; i++)
for(j = V; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
}
return 0;
}

1.2 完全背包问题

基本概念:与01背包不同的是,完全背包中每种物品的数量没有限制,可以无限使用。状态定义与01背包一致。

题目链接

已知硬币总重量,每种硬币的重量和面值,求硬币面值之和最小的可能值。

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
/*
状态转移方程:dp[i][j] = min(dp[i-1][j-n*v[i]] + n*w[i]), 0 <= n*v[i] <= j.
空间优化后:dp[j] = min(dp[j-n*v[i]] + n*w[i]), 0 <= n*v[i] <= j.
改进后:d[j] = min(dp[j], dp[j-v[i]] + w[i]), j >= v[i].
*/
#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 10005;
int dp[maxn];

int main(){
int T, P, W, E, F, N;
cin >> T;
while(T--){
cin >> E >> F;
int V = F - E;
cin >> N;
memset(dp, -1, sizeof(dp)); //初始化为-1,-1表示状态未到达
dp[0] = 0; //当下面循环中j = 0时,可以使得dp[W] = P。
int i, j;
for(i = 1; i <= N; i++){
cin >> P >> W;
for(j = 0; j <= V - W; j++){
if(dp[j] == -1) continue; //状态未达到,不能参考这个状态
else if(dp[j + W] == -1) dp[j + W] = dp[j] + P; //加上{P, W}这种情况的状态还未达到,就进行转移
else dp[j + W] = min(dp[j + W], dp[j] + P); //这种状态已经达到了,就取较小的
}
}
if(dp[V] == -1) //说明任何硬币组合都不能达到V的状态
cout << "This is impossible." << endl;
else
cout << "The minimum amount of money in the piggy-bank is " << dp[V] << "." << endl;
}
return 0;
}

1.3 多重背包问题

基本概念:多重背包的特点是物品的数量可以大于1但有限制。状态定义与01背包一致。

题目链接

已知手表价格大于0且不超过M,有N种硬币,已知每种硬币的价值和数量,求能用硬币支付的手表价格的情况有多少种。

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
//定义dp[i]为是否可以使面值之和为i。
//处理每种硬币时,转移次数与Ci有关,使得处理第i种硬币的复杂度是O(M*Ci),而当Ci较大时,复杂度较高。
/*
可以用二进制的方法优化,使得每种物品的转移次数变为O(M*log(Ci)),方法是将i种硬币分组,分别以1,2,4,...,2的n次方个硬币为一组,这些数相加等于Ci。可知,任意小于等于Ci的数都可以用这些数中的一部分(或全部)之和表示出来。将每一组的硬币面值相加作为一个硬币来处理,就可以转化为01背包问题来解决了。
*/
#include <iostream>
#include <string.h>
using namespace std;

int dp[100005], a[105], c[105], w[1005];

int main(){
int n, m;
while(cin >> n >> m && (n || m)){
memset(dp, 0, sizeof(dp)); dp[0] = 1;
int i, j;
for(i = 1; i <= n; i++)
cin >> a[i];
for(i = 1; i <= n; i++)
cin >> c[i];
int cnt = 0;
for(i = 1; i <= n; i++)
for(j = 1; c[i] > 0; j *= 2){ //对每种硬币进行分组,用j模拟2的幂(也可用移位,j <<= 1)
int t = min(j, c[i]); //若c[i]并不刚好是等比数列之和,那么多出来的部分小于j,这里考虑的是最后的情况
c[i] -= t;
w[cnt++] = a[i]*t; //记录该分组的硬币价值之和
}
int ans = 0;
for(i = 0; i < cnt; i++)
for(j = m; j >= w[i]; j--)
if(dp[j-w[i]])
dp[j] = 1;
for(i = 1; i <= m; i++)
ans += dp[i];
cout << ans << endl;
}
return 0;
}

2. 状态压缩

2.1 旅行商问题

题目链接

访问N座城市,共有M条路,必须访问所有的城市至少一次,并且访问次数不能超过两次(也就是1次或2次)。已知每条道路的费用,求最小费用,若不能完成就返回-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
//
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

int dp[60000][11], c[20][20], len[11];
#define Gets(i, j) (i/len[j])%3

int main(){
len[0] = 1;
for(int i = 1; i <= 10; i++)
len[i] = len[i-1] * 3;
int n, m, f, a, b, w, u, v, ans;
while(~scanf("%d%d", &n, &m)){
memset(c, 0x3f, sizeof(c));
memset(dp, 0x3f, sizeof(dp));
for(int i = 0; i < m; i++){
scanf("%d%d%d", &a, &b, &w);
a--; b--;
c[a][b] = c[b][a] = min(c[a][b], w);
}
ans = dp[0][0];
int i, j;
for(i = 0; i < n; i++)
dp[len[i]][i] = 0;
for(i = 1; i < len[n]; i++){
f = 1;
for(j = 0; j < n; j++){
if(Gets(i, j)==0){
f = 0;
continue;
}
for(int v = 0; v < n; v++){
if(Gets(i, v)==2)
continue;
u = i + len[v];
dp[u][v] = min(dp[u][v], dp[i][j] + c[j][v]);
}
}
if(f){
for(j = 0; j < n; j++)
ans = min(ans, dp[i][j]);
}
}
if(dp[0][0]==ans) ans = -1;
printf("%d\n", ans);
}
return 0;
}

2.2 插头dp

基本概念:插头dp也是状态压缩dp的一种,成为轮廓线dp。通常用于解决二维空间上的状态压缩问题,且约束条件是每个位置只需要关心与自己邻近的几个点。所以,应该按顺序逐个位置进行处理。

题目链接

1

3. 动态规划优化

3.1 数据结构优化

3.2 斜率优化

3.3 四边形不等式优化

4. 常见动态规划题目类型

4.1 树形dp

4.2 RMQ问题

4.3 有向图最短路

4.4 最长上升子序列

5. 习题解析的博客链接

hdu4576

题目

一个圆盘,有n个编号(1,2,3……n),从1出发,每次能逆时针或顺时针走w步,问经过m次后,最终停留在区间[l,r]的概率。

解析

首先,取模运算是一定要把1到n换成0到n-1;其次,利用temp来进行奇偶变换。

引用自博客:

https://www.cnblogs.com/kevinACMer/p/3723531.html

代码

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 1000005
int n, m, l, r;
double dp[205][2];
int w[maxn];
int main(){
while(scanf("%d%d%d%d", &n, &m, &l, &r) && (n || m || l || r)){
for(int i = 0; i < m; ++i) scanf("%d", &w[i]);
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int cur = 0;
for(int j = 0; j < m; ++j){
int t = w[j] % n;
cur ^= 1;
for(int i = 0; i < n; ++i)
dp[i][cur] = 0.5 * dp[(i + t) % n][cur ^ 1] + 0.5 * dp[(i - t) % n][cur ^ 1];
}
double ans = 0;
for(int i = l - 1; i < r; ++i) ans += dp[i][cur];
printf("%.4lf\n", ans);
}
return 0;
}

hdu1024

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1024

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
#define FI(a, b, c) for(int a = (b); a <= (c); a++)
#define FD(a, b, c) for(int a = (b); a >= (c); a--)
using namespace std;

int n, m, t;
long long d[1000005], l[1000005];

int main(){
while(scanf("%d %d", &m, &n) != EOF){
FI(i, 1, m) d[i] = l[i] = -1e15;

while(n--){
scanf("%d", &t);
FD(i, m, 1){
d[i] = max(d[i], l[i - 1]) + t;
l[i] = max(l[i], d[i]);
}
}
printf("%lld\n", l[m]);
}
}

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.