还记得我上上篇博客的DAGDP吗，这道题就是一个出色的实际应用。
题目传送门
https://vjudge.net/problem/UVA-1025
题意
也许你听说过巴比伦塔的传说。现在这个故事有很多细节已经被遗忘了。现在，根据这次比赛的教育性质，我们将告诉你们
整个故事:
巴比伦人有n种积木，每种积木都有无限的供应。每个i型块都是一个具有线性维数(xi)的矩形实体。一块可以重新定位，使它的三个维度中的任何两个决定基地的维度另一个维度是高度。他们想通过堆叠积木来建造最高的塔。问题是那就是，在建造一座塔的过程中，一个街区只能被放置在另一个街区的顶部，直到上部块的两个基本尺寸都严格小于相应的尺寸下块的基本尺寸。例如，这意味着，面向拥有的块等大小的碱基不能堆在一起。
你的工作是编写一个程序来确定巴比伦人能达到的最高塔的高度
用一组给定的块构建。
分析
题目稀里哗啦一大堆，其实原理就跟我们小时候的搭积木一样，我们每次搭一层就要保证上面积木的长和宽严格小于下面积木的长和宽，那么我们如何使高度最高呢？
首先因为这是个立方体，有高度的存在，所以不能直接按照边长排队，所以这题就麻烦很多了。毫无疑问的是，我们使用长宽的关系建图的思想是没有什么大问题的，而高度我们只需要后期比较就可以了，我们首先需要建立状态的表示方法，比如序号为i，长为a，宽为b，高为c，难道我们需要使用四元组来表示吗，其实我们可以用数组记下这些信息，但是我们状态转移只需要二维的序号+高就可以了，所以我们可以套用DAGDP的模板写出下面的代码
代码
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 <algorithm>
#include <cstring>
using namespace std;
int n;
int num[32][3],d[32][3];
void depart(int* m,int x, int y) {
int count = 0;
for(int i=0;i<3;i++) {
if (i != y)
m[count++] = num[x][i];
}
}
int dp(int x,int y){
if(d[x][y]>0)
return d[x][y];
d[x][y]=0;
int m1[2],m2[2];
depart(m1,x,y);
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
depart(m2,i,j);
if((m2[0]<m1[0]&&m2[1]<m1[1])||(m2[0]<m1[1]&&m2[1]<m1[0]))
d[x][y]=max(d[x][y],dp(i,j));
}
}
d[x][y]+=num[x][y];
return d[x][y];
}
int main() {
ios::sync_with_stdio(false);
for(int cas=1;cin>>n&&n;cas++) {
memset(d,0,sizeof(d));
int a,b,c;
for(int i=0;i<n;i++){
cin>>a>>b>>c;
num[i][0]=a;
num[i][1]=b;
num[i][2]=c;
}
int mx=0;
for(int i=0;i<n;i++)
for(int j=0;j<3;j++)
mx=max(mx,dp(i,j));
cout << "Case " << cas <<": maximum height = " << mx << endl;
}
return 0;
}
|