Algorithm - DP - DAG 模型

DAG 模型常常被应用于动态规划问题中,比较常见.

DAG (Directed Acyclic Graph)

DAG 就是有向无环图,其能够描述二元关系,可用于动态规划.

剖析

DAG 上的动态规划,许多仍然是记忆化搜索,但是搜索的对象是一个图.
如图所示,如果有这样一个 DAG,可发现 CCDD 被搜索了两次,因此可以直接记忆化.
对于大多数 DAG 上的动态规划,结点间有边权,因此往往求的是最短路、最长路.
DAG上的动态规划


例题

完全背包

已有背包的专题文章,可查看背包.

巴比伦塔 (UVa 437) UVa vjudge

问题描述

Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the
whole story:

The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-ii block was a rectangular solid with linear dimensions (xi,yi,zi)(x_i,y_i,z_i) . A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.
They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn’t be stacked.

Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks.

输入

The input file will contain one or more test cases. The first line of each test case contains an integer nn ,
representing the number of different blocks in the following data set. The maximum value for nn is 3030 .
Each of the next n lines contains three integers representing the values xi,yi,zix_i,y_i,z_i .
Input is terminated by a value of zero (00) for nn .

输出

For each test case, print one line containing the case number (they are numbered sequentially starting from 11) and the height of the tallest possible tower in the format
‘Case case: maximum height = height’

样例输入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
样例输出
1
2
3
4
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

思路

如果一个砖块能够放在另一个砖块上,那么这两个砖块有一条有向边,边权为上面砖块的高度.
此题主要要解决的是,砖块的底面不确定,因此我们需要将一个砖块拆解为三个不同底面的砖块,问题即可解决.
为了方便,建图时可引入虚结点,代表大地,方便搜索,以样例输入的最后一组数据的某两个砖块为例,如图所示.
Babylon

代码

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
#include <iostream>
#include <cstring>
#define MAXN (30+5)
#define MAX(a,b) (((a)>(b))?(a):(b))
int d[MAXN][3];
int x[MAXN], y[MAXN], z[MAXN];
int babylon_sub(int c, int rot, int n)
{
if(d[c][rot] != -1)
{
return d[c][rot];
}
d[c][rot] = 0;
int base1, base2;
if(rot == 0) { base1 = x[c]; base2 = y[c] }
if(rot == 1) { base1 = y[c]; base2 = z[c] }
if(rot == 2) { base1 = x[c]; base2 = z[c] }
for(int i = 0; i < n; i++)
{
if((x[i] < base1 && y[i] < base2) || (y[i] < base1 && x[i] < base2))
d[c][rot] = MAX(d[c][rot], babylon_sub(i, 0, n) + z[i]);
if((y[i] < base1 && z[i] < base2) || (z[i] < base1 && y[i] < base2))
d[c][rot] = MAX(d[c][rot], babylon_sub(i, 1, n) + x[i]);
if((x[i] < base1 && z[i] < base2) || (z[i] < base1 && x[i] < base2))
d[c][rot] = MAX(d[c][rot], babylon_sub(i, 2, n) + y[i]);
}
return d[c][rot];
}
int babylon(int n)
{
//memset(d, -1, sizeof(d));
for(int i = 0; i < n; i++)
{
d[i][0] = -1;
d[i][1] = -1;
d[i][2] = -1;
}
int r = 0;
for(int i = 0; i < n; i++)
{
r = MAX(r, babylon_sub(i, 0, n) + z[i]);
r = MAX(r, babylon_sub(i, 1, n) + x[i]);
r = MAX(r, babylon_sub(i, 2, n) + y[i]);
}
return r;
}
int main()
{
int t = 0;
while(true)
{
int n;
std::cin >> n;
if(n == 0) break;
t++;
for(int i = 0; i < n; i++)
{
std::cin >> x[i] >> y[i] >> z[i];
}
std::cout << "Case " << t << ":" << " maximum height = " << babylon(n);
std::cout << std::endl;
}
return 0;
}